Sorting Algorithm: Quick Sort

Sorting Algorithms

• Various sorting algorithms which we will study in this chapter are ‒

1. Insertion sort

2. Merge sort

3. Quick sort

4. Heap sort

 

Sorting Algorithm: Quick Sort

• Quick sort is a sorting algorithm that uses the divide and conquer strategy. In this method division is dynamically carried out. The three steps of quick sort are as follows:

1) Divide : Split the array into two sub arrays that each element in the left sub array is less than or equal the middle element and each element in the right sub array is greater than the middle element. The splitting of the array into two sub arrays is based on pivot element. All the elements that are less than pivot should be in left sub array and all the elements that are more than pivot should be in right sub array.

2) Conquer : Recursively sort the two sub arrays.

3) Combine : Combine all the sorted elements in a group to form a list of sorted elements.

• Consider an array A[i] where i is ranging from 0 to n ‒1 then we can formulize the division of array elements as

• Let us understand this algorithm with the help of some example.

 

Analysis

• When pivot is chosen such that the array gets divided at the mid then it gives the best case time complexity. The best case time complexity of quick sort is O(nlog ₂n).

• The worst case for quick sort occurs when the pivot is minimum or maximum of all the elements in the list. This can be graphically represented as ‒

• This ultimately results in O(n²) time complexity. When array elements are randomly distributed then it results in average case time complexity, and it is O(nlog₂n).

C++ program

/**************************************************************

Program to sort the elements in ascending order using Quick Sort

***************************************************************/

#include<iostream>

#include<cstdlib>

using namespace std;

#define SIZE 10

class Quick

{

  private:

    int arr[SIZE];

  public:

    int get _data(int);

    void quicksort(int,int);

    int partition(int,int);

    void swap(int,int);

    void display(int);

};

/*

This function is to input the elements

*/

int Quick::get_data(int n)

{

    int i;

    cout<<"\n Enter Total numbers to sort : ";

    cin>>n;

    for(i=0;i<n;i++)

    {

        cout<<"\nEnter Element";

        cin>>arr[i];

    }

    return n;

}

/*

This fuction is to sort the elements in a sublist

*/

void Quick::quicksort(int p,int q)

{

    int i; if(p<q)

    {

        j‒partition(p,q+1);//setting pivot element

        quicksort(p,j‒1);//splitting of list

        quicksort(j+1,q);//splitting of list

    }

}

/*

This function is to partition a list and decide the pivot element

*/

int Quick::partition(int m,int p)

{

    int pivot = arr[m];

    int i=m,j=p;

    do

    {

        do

        {

            do

                i++;

        }while(arr[i] <pivot);

        do

        {

            j‒ ‒;

        while(arr[j]>pivot);

        if(i<j)

            swap(i,j);

        }while(i<j);

        arr[m] = arr[j];

        arr[j]=pivot;

    return j;

}

void Quick::swap(int i,int j)

{

    int P;

    p=arr[i];

    arr[i] = arr[j];

    arr[j] = p;

}

void Quick::display(int n)

{

    for(int i=0;i<n;i++)

    cout<<" "<<arr[i];

}

void main()

{

    Quick obj://for integer elements

    int n,i;

    clrscr();

    cout<<"\n\t\t Quick Sort Method \n";

    n=obj.get data(n);

    obj.quicksort(0,n‒1);

    cout<<"\n\n\t Sorted Array Is: \n";

    obj.display(n);

    getch();

}

Output

Quick Sort Method

Enter Total numbers to sort: 5

Enter Element 30

Enter Element 50

Enter Element 10

Enter Element 20

Enter Element 40

Sorted Array Is:

10 20 30 40 50

 

Example : 1

Explain the algorithm of quick sort by sorting the following set of numbers as an example:

42  47  52  57  62  37  32  27 22.

Solution:

Step 1:

Step 2:

As Array[i] > Array[pivot], i will not be incremented. As Array [j] < Array[pivot], j will not be decremented. Just swap Array[i] and Array[j]. increment i, decrement j

Step 3:

As Array[i] > Array[pivot], i will not be incremented. As Array[j] < Array[pivot], j will not be decremented.

 Just swap Array[i] and Array[j]. Then increment i and decrement j.

Step 4:

Swap Array[i] and Array [j]

Step 5 :

Swap Array[i] and Array[j]

Step 6 :

As j <i, swap Array[Low] and Array[j]

Step 7 :

Step 8:

Now two sublist can be sorted independantly.

While Array[i] < Array[pivot] keep on incrementing i as i = j, swap Array[j] and Array[pivot]

Step 9 :

Step 10 :

Sort the left sublist obtained in step 9.

Step 11 :

We will sort left sublist obtained in step 9.

Swap Array[pivot] and Array[j]

Step 12 :

The left sublist obtained in step 7 is now sorted.

We will sort right sublist

Go on incrementing i if Array[i] < Array[pivot]

Step 13 :

Swap Array[pivot] and Array[j]

Step 14 :

Step 15 :

Now we will sort the left sublist obtained in step 13.

Now swap Array[i] and Array[j].

Thus we get a sorted sublist.

Step 16 :

If we combine all the sublist we get following list ‒

This is a sorted list.

 

Example : 2

Sort the following values using Quick sort and estimate its time and space complexity: 65 70 75 80 85 60 55 50 45. Illustrate each step of the sorting process.

Solution :

Pass 1

(55, 50, 45) 60 (65 70 75 80 85)

Pass 2

45 (55, 50) (65, 70, 75, 80, 85)

Pass 3

45, 50, 55 (65, 70, 75, 80, 85)

Pass 4

45 50 55 65 (70 75 80 85)

Pass 5

45 50 55 65 70 (75 80 85)

Pass 6

45 50 55 65 70 75 (80 85)

Pass 7

45 50 55 65 70 75 80 (85)

Pass 8

45 50 55 65 70 75 80

 

Example : 3

Discuss the quick sort algorithm and apply the same for the following numbers, 90, 77, 60, 99, 55, 88, 66.

Solution:

Quick sort Algorithm ‒ Refer section 9.5.

Consider the elements in an array

The first element is considered to be pivot element.

Step 1:

Similarly if A[j] > A[pivot] decrement j.

As i can not be incremented or j can not be decremented. Hence swap A[i] and A[j]. Then continue to increment i and decrement j. When j crosses i, swap A[j] and A[pivot].

Step 2:

Step 3 :

Step 4 :

Step 5 :

Step 6 :

Step 7 :

Consider the Right sub‒list obtained in step 2.

Step 8:

Obtaining the sublists from all the previous steps we get the final sorted list as

 

Review Questions

1. Write C++ code to implement quick sort with suitable example.

2. Give short notes of quick sort with suitable example.

3. Explain quick sort in detail.

4. Write a C++ program to implement quick sort.