Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 10: Problem 10

Write a PRAM algorithm for Quicksort using \(n\) processors to sort a list of \(n\) elements.

Short Answer

Expert verified
A PRAM Quicksort algorithm involves the selection of a pivot element, the parallel division of the array elements into groups ('low' and 'high'), and the parallel calculation of prefix sums to decide where elements will be placed after partitioning. Both 'low' and 'high' sublists are then recursively sorted in parallel, after which, they are combined in the correct order to produce the sorted list as output.

Step by step solution

01

Initialize Input Array

Start by initializing an unsorted array with n elements that needs to be sorted.
02

Pivot Selection

Choose the pivot element. This could be the first, the last, the median, or any random element. Its choice doesn't affect the parallelization but can affect the speed of the algorithm.
03

Split into Groups

Split the array into two groups, with one processor assigned to each element of the array. Each processor compares its element with the pivot: if it's less than or equal to the pivot, it puts its element into the 'low' group; if it's greater, it goes into the 'high' group.
04

Calculate Prefix Sums

To find out where to put their elements in the new array, processors calculate prefix sums on a boolean vector where 1 indicates a 'low' element and 0 indicates a 'high' element. The prefix sum of an element gives the new position for a 'low' element, and for a 'high' element, it's found by subtracting the prefix sum from the total number of 'low' elements.
05

Perform Write

Each processor now knows where to write its element, so it performs the write, creating a new array that has 'low' elements followed by 'high' elements.
06

Quicksort Sublists

Recursively apply Quicksort to each of the 'low' and 'high' sublists using a divide-and-conquer approach. If a sublist has more than one element, use the PRAM Quicksort algorithm on that sublist. If a sublist has one element, no need to sort it.
07

Combine Results

After the recursive Quicksort calls are finished, combine the sorted 'low' and 'high' sublists into a single sorted list. Since the 'low' and 'high' sublists are already in the correct order relative to each other (all 'low' elements are less than or equal to all 'high' elements), no merging is needed. We just concatenate the 'low' sublist in front of the 'high' sublist.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Consider the problem of adding \(n\) numbers of a list. If it takes \(t_{a}\) time for one person to add two numbers, and it takes no time to pass the result of an addition from one person to another, how many people do we need to minimize the total time spent to get the final answer? What will be the minimum amount of time needed to find the answer if we have enough people? Justify your answer.

Write a CRCW PRAM algorithm that uses \(n^{2}\) processors to multiply two \(n \times n\) matrices. Your algorithm should perform better than the standard \(\Theta\left(n^{3}\right)\) -time serial algorithm.

Write a scquential algorithm that implements the Tournament Method to find the largest key in an array of \(n\) keys. Show that this algorithm is no more efficient than the standard sequential algorithm.

Write a PRAM algorithm that runs in \(\Theta(\lg n)^{2}\) ) time for the problem of mergesorting. (Hint: Use \(n\) processors, and assign each processor to a key to determine the position of the key in the final list by binary searching.)

Assuming that one person can add two numbers in \(t_{e}\) time, how long will it take that person to add all \(n\) numbers of a list considering the operation of addition as the basic operation? Justify your answer.
See all solutions

Recommended explanations on Computer Science Textbooks

Databases

Read Explanation

Algorithms in Computer Science

Read Explanation

Computer Programming

Read Explanation

Computer Systems

Read Explanation

Theory of Computation

Read Explanation

Data Structures

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free