Quick Sort

Quick Sort

It is also called partition exchange sort because it works by partitioning the array to be sorted.

Basic Idea:

1. Let x be an array and n be the number of elements in the array.
2. Let us choose an element (called pivot) a from a specific position within the array (for example, a can be chosen as the first element so that a=x[o]).
3. Now suppose that the elements of array x are partitioned in such a way that a is placed into position j of the array and the following conditions hold:

• Each of the elements in positions j through j-1 is less than or equal to a.
• Each of the elements in positions j+1 through n-1 is greater than or equal to a.

1. If these two conditions hold for a particular a and j, a is the jth smallest element of array x, so that remains in position j when the array is completely sorted.
2. lf the same process is repeated for sub-arrays x[o] through x[j-1] and x[j+1] through x[n-1] and any sub arrays created by the process in successive iterations, the final result is a sorted file.
3. This is the divide-and-conquer approach used in quick sort.
4. This procedure is called divide-and-conquer because the problem is first divided into two or more instances of the same problem of smaller size and then the problem is conquered by using the solutions of the smaller problems to find a solution of the original problem.

Working of Quick Sort

1. Let a=x[lb] be the pivot element whose exact final position is required.
2. There are two pointers, up and down, that are initialized to the upper and lower bounds of the sub-array, respectively.
3. At any point during execution, each element in a position above up is greater than or equal to a, and each element in a position below down is less than or equal to a.
4. The two pointers up and down are moved towards each other in the following fashion:

• Step 1: Repeatedly increase the pointer down by one position while x[down]<=a.
• Step 2: Repeatedly decrease the pointer up by one position while x up >a.
• Step 3: If down

This process is repeated until the condition in step 3 fails (down>=up), at which point x[ up] is interchanged with x[lb] (which equals pivot element a), whose final position was required, and the process is repeated again recursively For the two sub-arrays on the left and right of the pivot element a.

Efficiency of Quick Sort

1. Let us assume that the file size n is a power of 2, say n=2^m. Thus m=log₂n.
2. Let us also assume that the proper position of the pivot always turns out to be the exact middle of the sub array.
3. In that case there are approximately n comparisons on the first pass, after which the file is split into two sub files each of size n/2, approximately. For each of these two files there are approximately n/2 comparisons and a total of four files each of size n/4
4. are formed. Each of these files requires n/4 comparisons yielding a total of n/8 sub files. After halving the sub files m times, there are n files of size 1.
5. Thus the total number of comparisons for the entire sort is approximately
6.  n + 2.*(n/2.) + 4*(n/4) + 8*(n/8) +... + n*(n/n)  = n+ n + n + n +...+n (m terms) comparisons.
7. There are m terms because the file is subdivided m times.
8. Thus the total number of comparisons is O(n*m) or O(n log n)
9. Thus the efficiency of quick sort is O(n log n), which is better than bubble or selection or insertion sort.

C Program For Quick Sort

#include <stdio.h>
void quicksort(int number[25], int first, int last)
{
    int i, j, pivot, temp;
    if (first < last)
    {
        pivot = first;
        i = first;
        j = last;
        while (i < j)
        {
            while (number[i] <= number[pivot] && i < last)
                i++;
            while (number[j] > number[pivot])
                j--;
            if (i < j)
            {
                temp = number[i];
                number[i] = number[j];
                number[j] = temp;
            }
        }
        temp = number[pivot];
        number[pivot] = number[j];
        number[j] = temp;
        quicksort(number, first, j - 1);
        quicksort(number, j + 1, last);
    }
}
int main()
{
    int i, count, number[25];
    printf("How many elements are u going to enter?: ");
    scanf("%d", &count);
    printf("Enter %d elements: ", count);
    for (i = 0; i < count; i++)
        scanf("%d", &number[i]);
    quicksort(number, 0, count - 1);
    printf("Order of Sorted elements: ");
    for (i = 0; i < count; i++)
        printf(" %d", number[i]);
    return 0;
}

Related Posts

Insertion Sort

Merge Sort

Bubble Sort

Selection Sort

Quick Sort

C Program For Bubble Sort | C Programming

C Program For Selection Sort | C Programming

C Program For Quick Sort | C Programming

C Program For Merge Sort | C Programming

C Program for Insertion Sort | C Programming