Helsinki University of Technology
Laboratory of Information Processing Science
Tik-76.122 Data Structures and Algorithms
demo

Assignment 2 (2 points)

Quickselect is an algorithm that finds the k:th smallest item from an array in linear time. Quickselect is based on quicksort algorithm ( Fig 7.16 Qselect), but the Median3-pivot is not used.

The string arrays below represent the original string S (length = 28) and the string P after the first phase of partitioning procedure when Quickselect is used for finding the median.

Continue the partitioning method to find the median and represent the string A after the next step. Represent only those items which belongs to the partition. Items out of the partition are left empty. The pivot item is picked from the right end and it belongs to the partition. Otherwise the algorithm is the same as in the text book (Fig. 7.16).

You can send an answer to this assignment at most 1 times.

Example

Suppose that the original string and the string after the first phase of partitioning are as follows:

		A S O R T I N G E X A M P L E
		A A E E T I N G O X S M P L R

The answer to the assignment would be:

		. . . . L I N G O P M R X T S