Sorting Techniques - Quick Sort (Partition Exchange Sort)

Q.1) What is the working of Quick Sort?

Quick Sort method sorts one element at a time. The element selected for sorting called pivot element will be placed in array at its proper position such that to the left of it all elements are smaller or equal and to the right all elements are greater (in case of ascending sorting). An array will be divided into two parts at sorted position of the pivot and sorting continues with sub - arrays by selecting pivot element.

Q.2) What is the purpose of partition in Quick Sort?

The purpose of partition is to allow a specific element to find its proper position with respect to the others in the subarray. It allows sorting to be performed on only subarray resulting into fewer elements in memory. It is highly efficient to sort large data sets by dividing them into smaller sub arrays.

Q.3) Why Quick Sort is best suitable in virtual memory environment?

Virtual memory is an extension of RAM to hold data which is not needed immediately, but can be accessed any time. Such data is stored in part of secondary storage (disk) which is considered part of RAM. As quick sort partitions array into sub-arrays and sorts one sub-array at a time, other sub arrays can be stored in secondary storage to avoid unnecessary occupation of memory. This method allows better utilization of memory, hence Quick Sort is best suitable for virtual memory environment.

Q.4) Write a function to implement partitioning process of Quick Sort.

#define MAXSZ 10

int partition(int a[], int lb, int ub)

{

    int down = 0, up = ub;

    int pivot = a[lb], hold;

    while (down < up)

    {

        while (a[down] <= pivot && down < ub) down++;

        while (a[up] > pivot) up--;

        if (down < up)

        {

            hold = a[down];

            a[down] = a[up];

            a[up] = hold;

        }

    }

    a[lb] = a[up];

    a[up] = pivot;

    return up;

}

Q.5) How efficient is the Quick Sort in terms of time complexity?

If we consider the file size (or array size) n is a power of 2 ( n = 2-square), so that m = log n (log n to the base 2).If we assume proper position of pivot element always turns out to be exact middle of the sub-array. Then first pass has an array of size n and comparisons are (n-1) , this array splits after placing pivot element at its proper position resulting into 2 sub-arrays of size approximately n/2, which means 2*(n/2) comparisons in next pass.

n+ 2*(n/2) + 2*(n/3) + .............+ n*(n/n)

OR

n + n + n + ........+ n (m terms) where m = log n.

An efficiency of Quick Sort is O(n*m) OR (n * log n).

n are the comparisons and log n (log n to the base 2) are passes.

Q.6) What is the best case, average case and worst case of Quick Sort ? What is the time complexity for all three cases?

Best Case - Unsorted Data with pivot element position turns out be exactly middle of sub array always (Uniform distribution of elements) - O(n log n)

Average Case - Unsorted Data - O (n log n)

Worst Case - Sorted data in the same order or it is oppositely sorted (data is sorted in any order ascending or descending ) - O(n-square)

Q.7) What is the space complexity of Quick Sort?

Quick sort needs to hold n elements and one extra memory location for swapping. Hence, its space complexity is O(n+1).

Q.8) What is the similarity between Quick Sort and Bubble Sort?

Quick Sort and Bubble Sort both methods are known as exchange sort methods. Both methods need not only comparison but also exchanging of elements (swapping).

Q.9) What are the advantages of Quick Sort?

Q.10) Write a function Quick Sort?

#define MAXSZ 10

int partition(int a[], int lb, int ub)

{

    int down = 0, up = ub;

    int pivot = a[lb], hold;

    while (down < up)

    {

        while (a[down] <= pivot && down < ub) down++;

        while (a[up] > pivot) up--;

        if (down < up)

        {

            hold = a[down];

            a[down] = a[up];

            a[up] = hold;

        }

    }

    a[lb] = a[up];

    a[up] = pivot;

    return up;

}

void quicksort(int a[], int lb, int ub)

{

    int pos;

    if (lb < ub)

    {

        pos = partition(a,lb,ub);

        quicksort(a,lb,pos-1);

        quicksort(a,pos+1,ub);

    }

}

Q.11) Sort following integers using Quick Sort method.

Want to read more?

Subscribe to questionbankos.com to keep reading this exclusive post.

Subscribe Now