Quick Sort

The quick sort uses divide and conquer to gain the same advantages as the merge sort, while not using additional storage. As a trade-off, however, it is possible that the list may not be divided in half. When this happens, we will see that performance is diminished.

A quick sort first selects a value, which is called the pivot value. Although there are many different ways to choose the pivot value, we will simply use the first item in the list. The role of the pivot value is to assist with splitting the list. The actual position where the pivot value belongs in the final sorted list, commonly called the split point, will be used to divide the list for subsequent calls to the quick sort.

Following shows that 54 will serve as our first pivot value. Since we have looked at this example a few times already, we know that 54 will eventually end up in the position currently holding 31. The partition process will happen next. It will find the split point and at the same time move other items to the appropriate side of the list, either less than or greater than the pivot value.

54 26 93 17 77 31 44 55 20 (54 will be the first pivot)

Partitioning begins by locating two position markers—let’s call them leftmark and rightmark—at the beginning and end of the remaining items in the list (positions 1 and 8 above). The goal of the partition process is to move items that are on the wrong side with respect to the pivot value while also converging on the split point. Following elements showing this process as we locate the position of 54.

Step1: leftmark and rightmark will converge on split point

54 26 93 17 77 31 44 55 20

Step 2: 26 < 54 move to right 93 > 54 stop.

54 26 93 17 77 31 44 55 20

Step 3:Now, rightmark 20 < 54 stop

54 26 93 17 77 31 44 55 20

Step 4: Exchange 20 and 93

54 26 20 17 77 31 44 55 93

Step 5:Now, continue moving leftmark and rightmark 77 > 54 stop, 44 < 54 stop , exchange 77 and 44.

54 26 20 17 77 31 44 55 93

Step 6: 77 > 54 stop, 31 < 54 stop, rightmark < leftmark split point found exchange 54 and 31.

54 26 20 17 44 31 77 55 93

We begin by incrementing leftmark until we locate a value that is greater than the pivot value. We then decrement rightmark until we find a value that is less than the pivot value. At this point we have discovered two items that are out of place with respect to the eventual split point. For our example, this occurs at 93 and 20. Now we can exchange these two items and then repeat the process again.

At the point where rightmark becomes less than leftmark, we stop. The position of rightmark is now the split point. The pivot value can be exchanged with the contents of the split point and the pivot value is now in place Following In addition, all the items to the left of the split point are less than the pivot value, and all the items to the right of the split point are greater than the pivot value. The list can now be divided at the split point and the quick sort can be invoked recursively on the two halves.

31 26 20 17 44 54 77 55 93 (54 in place)

Quicksort left half Quicksort right half

31 26 20 17 44 77 55 93

Listing: Following program is showing implementation of Quick sort.

/* 
* C Program to Perform Quick Sort on a set of Entries 
* using Recursion 
*/ 
#include <stdio.h> 

void quicksort (int [], int, int); 

int main() 
{ 
    int list[50]; 
    int size, i; 

    printf("Enter the number of elements: "); 
    scanf("%d", &size); 
    printf("Enter the elements to be sorted:\n"); 
    for (i = 0; i < size; i++) 
    { 
        scanf("%d", &list[i]); 
    } 
    quicksort(list, 0, size - 1); 
    printf("After applying quick sort\n"); 
    for (i = 0; i < size; i++) 
    { 
        printf("%d ", list[i]); 
    } 
    printf("\n"); 

    return 0; 
} 
void quicksort(int list[], int low, int high) 
{ 
    int pivot, i, j, temp; 
    if (low < high) 
    { 
        pivot = low; 
        i = low; 
        j = high; 
        while (i < j) 
        { 
            while (list[i] <= list[pivot] && i <= high) 
            { 
                i++; 
            } 
            while (list[j] > list[pivot] && j >= low) 
            { 
                j--; 
            } 
            if (i < j) 
            { 
                temp = list[i]; 
                list[i] = list[j]; 
                list[j] = temp; 
            } 
        } 
        temp = list[j]; 
        list[j] = list[pivot]; 
        list[pivot] = temp; 
        quicksort(list, low, j - 1); 
        quicksort(list, j + 1, high); 
    } 
} 

Output: 

    Enter the number of elements: 6 
    Enter the elements to be sorted: 
    67 
    45 
    24 
    98 
    12 
    38 
    After applying quick sort 
    12 24 38 45 67 98