Quick Sort Algorithm

Quick Sort Algorithm

There are may versions of Quick sort, which is one of the most popular sorting methods due to its speed (O(N lgN) average, but O(N^2) worst case). Here’s the steps to follow:

  • Pick a “pivot” item
  • Partition the other items by adding them to a “less than pivot” sublist, or “greater than pivot” sublist
  • The pivot goes between the two lists
  • Repeat the quicksort on the sublists, until you get to a sublist of size 1 (which is sorted).
  • Combine the lists — the entire list will be sorted

Quicksort is the quickest and one of the most efficient sorting algorithm. Similar to Merge sort, Quick sort follows Divide and conquer algorithm to sort the given array.

The quicksort algorithm is a sorting algorithm that sorts an array by choosing a pivot element, and partition the array around the pivot such that

Elements smaller than the pivot are moved to the left of pivot, and elements larger than the pivot are moved to the right of pivot.

It continues to choose a pivot element and break down the array into single-element array, before combing them back together to form a single sorted array.

 

Working Model of Quick Sort

quick-sort-algorithm
quick-sort-algorithm

Time Complexity of Quick Sort

Since similar to Merge sort, Quick sort follows divide and conquer algorithm, its complexity in average and best case is same as that of Merge sort which is O(nlogn).

Whereas in the worst case, its complexity is O(n2). This occurs when the given array is nearly or completely sorted.

 

Complexity Analysis of Quick Sort

For an array, in which partitioning leads to unbalanced sub arrays, to an extent where on the left side there are no elements, with all the elements greater than the pivot, hence on the right side.

And if keep on getting unbalanced sub arrays, then the running time is the worst case, which is O(n2)

Where as if partitioning leads to almost equal sub arrays, then the running time is the best, with time complexity as O(n*log n).

Worst Case Time Complexity [ Big-O ]: O(n2)

Best Case Time Complexity [Big-omega]: O(n*log n)

Average Time Complexity [Big-theta]: O(n*log n)

Space Complexity: O(n*log n)

 

 

Implementing Quick Sort Algorithm

Below we have a simple C program implementing the Quick sort algorithm:

// simple C program for Quick Sort
# include <stdio.h>

// to swap two numbers
void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

/*  
    a[] is the array, p is starting index, that is 0, 
    and r is the last index of array.  
*/
void quicksort(int a[], int p, int r)    
{
    if(p < r)
    {
        int q;
        q = partition(a, p, r);
        quicksort(a, p, q);
        quicksort(a, q+1, r);
    }
}

int partition (int a[], int low, int high)
{
    int pivot = arr[high];  // selecting last element as pivot
    int i = (low - 1);  // index of smaller element
 
    for (int j = low; j <= high- 1; j++)
    {
        // If current element is smaller than or equal to pivot
        if (arr[j] <= pivot)
        {
            i++;    // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// function to print the array
void printArray(int a[], int size)
{
    int i;
    for (i=0; i < size; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

int main()
{
    int arr[] = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    // call quickSort function
    quickSort(arr, 0, n-1);
    
    printf("Sorted array: n");
    printArray(arr, n);
    return 0;
}

 

For any query or issue, feel free to discuss on http://discuss.eduguru.in