CODEWITHSUNDEEP
algorithmquicksort
Sravs2725
Sravs2725

Reputation: 21

What is the difference between quick sort algorithm and quick select algorithm?

Apart from searching only one side of array, are there any differences between quick sort and quick select?

Upvotes: 2

Views: 6224

Answers (2)

Yilmaz
Yilmaz

Reputation: 49729

both algorithms are divide and conquer algorithms any created by Tony Hoare.

In bot algorithms, we partition array from the pivot element into 2 arrays.

[el-1,el-2,....el-pivot,.......,el-last]

we know that elements that are on the left side of "el-pivot" are smaller than "el-pivot" but they are not sorted. So we apply quick sort to both subarrays in quick sort algorithm

In quick select, we do not sort the array. quick select algorithm is specifically for finding the kth smallest element in the array. We know that all the elements on the left side of el-pivot are smaller than el-pivot, so we dont care about sorting the left side, therefore we dont divide the left side. This reduces the complexity from O(nlog2(n)) to O(n)

Upvotes: 0

rcgldr
rcgldr

Reputation: 28941

One difference is that since only one partition is searched for on each level, then iteration can be used instead of recursion. Example code using Lomuto partition scheme. A better pivot choice (rather than a[hi]) would help depending on data pattern.

int QuickSelect(int a[], int sz, int k)
{
    int lo = 0;
    int hi = sz-1;              // (no check for empty array)
    while (lo < hi){
        int p = a[hi];          // Lomuto partition
        int i = lo;
        for (int j = lo; j < hi; ++j){
            if (a[j] < p){
                std::swap(a[j], a[i]);
                ++i;
            }
        }
        std::swap(a[i], a[hi]);
        if (k == i)             // if pivot == kth element, return it
            return a[k];
        if (k < i)              // loop on partition with kth element
            hi = i - 1;
        else
            lo = i + 1;
    }
    return a[k];                // sorted to kth elemement, return it
}

Upvotes: 1

Related Questions