Using the all three Quick Sort function, complete and run the program Quick Sort

Question

Using the all three Quick Sort function, complete and run the program Quick Sort to sort a set of N random numbers. Main function should generate the random numbers.

In order to generate random numbers you may like to do the following:

Apart from including iostream, you need to include the header file ctime.

In main, first call srand function as below.

srand(time(0));

Then populate your array A in main as below:

for(I = 1; I <= N; I++)

{

A[I] = rand();

}

Now use an integer variable, call it Option. Get user input for Option.

Include this variable Option as another parameter within your QuickSort, so QuickSort will have 4 parameters: A, first, last, option

Call QuickSort from main by using arguments: A, 1, N, option as

QuickSort(A, 1, N, option)

This way you can run different partition algorithm.

Run your code with all three option values: 1, 2 and 3

In main display the three different options as:

Option 1: Last Element as pivot

Option 2: First Element as pivot

Option 3: Random element as pivot

Any other value for Option, display a message invalid option and come out from code by using exit(0) command.

Make modification to your code to run all 4 types of data:

a) integers

b) characters

c) floating point numbers

d) strings

This can be done easily by making change in the typedef command

typedef int Data; // change int to char for character data, to string for strings, double for floats.

Explanation / Answer

QuickSort

Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.

Pseudo Code for recursive QuickSort function :

Partition Algorithm
There can be many ways to do partition, following pseudo code adopts the method given in CLRS book. The logic is simple, we start from the leftmost element and keep track of index of smaller (or equal to) elements as i. While traversing, if we find a smaller element, we swap current element with arr[i]. Otherwise we ignore current element.

Pseudo code for partition()

Illustration of partition() :

Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.

Implementation:
Following are C++, Java and Python implementations of QuickSort.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.