what is quicksort and how does it work? video of cards sorted by quick sort

sorting_quicksort_anim

Pick an element from the array (the pivot), partition the remaining elements into those greater than and less than this pivot, and recursively sort the partitions. There are many variants of the basic scheme above: to select the pivot, to partition the array, to stop the recursion on small partitions, etc.

Quick-sort is a randomized sorting algorithm based on the divide-and-conquer method.

The worst-case efficiency of the quick sort, O(n2), occurs when the list is sorted and the left-most element is chosen. Randomly choosing a pivot point rather than using the left-most element is recommended if the data to be sorted isn’t random. As long as the pivot point is chosen randomly, the quick sort has an algorithmic complexity of O(nlogn).

Video of how quick sort works with cards:

View This Video on You Tube

The quick sort is by far the fastest of the common sorting algorithms. It’s possible to write a special-purpose sorting algorithm that can beat the quick sort for some data sets, but for general-case sorting there isn’t anything faster. Quick sort is not stable. The worst-case space-complexity is O(N), but it can be limited to O(log(N)) if the code is modified.

#include 
using namespace std;

int a[10];
int partition(int left, int right);
void swap(int i, int j);
void sort(int i, int j);

int main()
{
int i,j=0,k=9;
for(i=0;i<10;i++) cin >> a[i];

sort(j,k);
for(i=0;i<10;i++)
cout << a[i] << endl; } void sort(int left, int right) { int p; if(left>=right)
return;
p = partition(left, right);

sort(left,p-1);
sort(p+1,right);
}

int partition(int left, int right)
{
int first=left, pivot=right–;
while(left<=right)
{
while(a[left]<a[pivot]) left++; while((right>=first)&&(a[right]>=a[pivot]))
right–;
if(left<right)
{
swap(left,right);
left++;
}
}
if(left!=pivot)
swap(left,pivot);

return left;
}

void swap(int i, int j)
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}

One thought on “what is quicksort and how does it work? video of cards sorted by quick sort

  1. bijesh March 30, 2007 at 2:41 am

    Minor correction in code. Change right- to right–. Good one!

Comments are closed.