/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} Problem 10 Write a PRAM algorithm for Quick... [FREE SOLUTION] | 91影视

91影视

Log out

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.

Over 30 million students worldwide already upgrade their learning with 91影视!

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

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.

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

Consider the problem of adding the numbers in a list of \(n\) numbers, If it takes \(t_{d}(n-1)\) time for one person to add all \(n\) numbers, is it possible for \(m\) people to compute the sum in less than \(\left[t_{e}(n-1)\right] / m\) time? Justify your answer.

Write a PRAM algorithm using \(n^{3}\) processors to multiply two \(n \times n\) matrices. Your algorithm should run in \(\Theta(\lg n)\) time.
See all solutions

Recommended explanations on Computer Science Textbooks

Big Data

Read Explanation

Databases

Read Explanation

Problem Solving Techniques

Read Explanation

Issues in Computer Science

Read Explanation

Data Structures

Read Explanation

Theory of Computation

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.