Programming Praxis

4 Responses to “Quick Sort”

1. Joe Doliner said

   November 10, 2009 at 8:05 AM

   Quicky python solution:

   def qsort(A):
   if (len(A) < 2):
   return A
   else:
   return qsort(filter(lambda x: x A[0], A[1:]))
   [/sourcecode]
2. Joe Doliner said

   November 10, 2009 at 8:06 AM

   Whoops messed up the formatting.
   Quicky python solution:

   def qsort(A):
   	if (len(A) < 2):
   		return A
   	else:
   		return qsort(filter(lambda x: x <= A[0], A[1:])) + [A[0]] + qsort(filter(lambda x: x > A[0], A[1:]))
   
3. Jebb said

   February 18, 2010 at 11:52 PM

   Ongoing experimentations in C. I’d implemented an integer version of this a few months ago, and I just went back and generalized it now I’ve learned how function pointers and (void *) passing works.

   static int swap(void *el1, void *el2, int elemSize)
   {
       void *buffer;
       buffer = (void *)malloc(elemSize * sizeof(char));
       assert(buffer);
       memcpy(buffer, el1, elemSize);
       memcpy(el1, el2, elemSize);
       memcpy(el2, buffer, elemSize);
       free(buffer);
   }
   
   static int partition(void *base, int length, int elemSize, void *pivot,
                   int (*cmpFunc)(void *, void *)) 
   {
   int i, newIndex;
       void *elt1, *elt2, *lastElt;
       lastElt = (char *)base + (length - 1) * elemSize;
       swap(pivot, lastElt, elemSize); //Move the pivot out of the way
       newIndex = 0;
       elt1 = base;
       for (i = 0; i < length - 1; i++) {  //We're storing the pivot at the end!!!
           elt2 = (char *)base + i * elemSize;
           if (cmpFunc(lastElt, elt2) < 0) {
               swap(elt1, elt2, elemSize);
               newIndex++;
               elt1 = (char*)base + newIndex * elemSize;
           }   
       }   
       /*Now we only need to re-insert the pivot (which we've stored at lastElt)
       *in the array at the proper index
       *With the numbering used, newIndex is now the index of the first element
       *"larger" than the pivot
       *elt1 is still the array element of index newIndex*/
       swap(lastElt, elt1, elemSize);
       return newIndex;
   }
   
   int quisort(void *base, int length, int elemSize, int (*cmpFunc)(void *, void *)) 
   {
       int pivotNewIndex;
       void *pivot, *base2;
       if (length > 1) {
           srand(time(0));
           pivot = (char *)base + (rand() % length) * elemSize;
           pivotNewIndex = partition(base, length, elemSize, pivot, cmpFunc);
           base2 = (char *)base + (pivotNewIndex + 1) * elemSize;
           quisort(base, pivotNewIndex, elemSize, cmpFunc);
           quisort(base2, length - pivotNewIndex - 1, elemSize, cmpFunc);
       }   
       return 0;
   }
4. Vikas Tandi said

   April 28, 2011 at 1:24 PM

   generating random every is very costly and slows down the algorithm considerably.
   I have used the median of three elements instead.
   Here is my c implementation

   #include <stdlib.h>
   #include <time.h>
   
   #define M 10
   
   void insertion_sort(int arr[], int left, int right);
   static void swap(int arr[], int i, int j);
   static int partition(int arr[], int left, int right);
   static void quicksort_imp(int arr[], int left, int right);
   
   /* assume presence of two artificial keys arr[0] = -ve infinity
   	and arr[n+1] = +ve infinity such that arr[0] <= arr[i] <= arr[n+1]
   	for 1 <= i <= n */
   void quicksort(int arr[], int left, int right)
   {
   	/* if array size is small or equal to M than
   		sort it directly by straight insertion sort */
   	if((right-left-1) > M)
   		quicksort_imp(arr, left+1, right-1);
   
   	if(M > 1)
   		insertion_sort(arr, left+1, right-1);
   }
   
   static void quicksort_imp(int arr[], int left, int right)
   {
   	int pivot, mid;
   
   	/* select pivot element */
   	mid = (left + right)/2;
   	pivot = (left + mid + right)/3;
   
   	/* swap pivot element with the first element */
   	swap(arr, left, pivot);
   
   	/* partition the array */
   	pivot = partition(arr, left, right);
   
   	/* right subfile is greater than or equal to left subfile and both subfiles are greater than M */
   	if((right - pivot) >= (pivot - left)	&&
   		(right - pivot) > M					&&
   		(pivot - left) > M)
   	{
   		/* sort the smaller subfile first to ensure that the stack size doesn't grow
   		more than log N */
   		quicksort_imp(arr, left, pivot-1);
   		quicksort_imp(arr, pivot+1, right);
   	}
   
   	/* left subfile is greater than right subfile and also both subfiles are greater than M */
   	if((pivot - left) > (right - pivot) 	&&
   		(right - pivot) > M					&&
   		(pivot - left) > M)
   	{
   		/* sort the smaller subfile first to ensure that the stack size doesn't grow
   		more than log N */
   		quicksort_imp(arr, pivot+1, right);
   		quicksort_imp(arr, left, pivot-1);
   	}
   
   	/* right subfile is greater than left subfile, right subfile is greater than M
   		and left subfiles is less than or equal to M */
   	if((right - pivot) > (pivot - left)	&&
   		(right - pivot) > M				&&
   		(pivot - left) <= M)
   	{
   		quicksort_imp(arr, pivot+1, right);
   	}
   
   	/* left subfile is greater than right subfile, left subfile is greater than M
   		and right subfiles is less than or equal to M */
   	if((pivot - left) > (right - pivot)	&&
   		(pivot - left) > M				&&
   		(right - pivot) <= M)
   	{
   		quicksort_imp(arr, left, pivot-1);
   	}
   
   	/* if both subfile are smaller than M, unwind the stack */
   }
   
   static int partition(int arr[], int left, int right)
   {
   	int i, j, key;
   
   	/* partition the element */
   	for(i = left, j = right+1, key = arr[left]; ;)
   	{
   		/* compare key with arr[i] */
   		for(i = i+1; arr[i] < key; i++);		/* the loop must terminate with i <= j as arr[j] >= key */
   
   		/* compare key with arr[j] */
   		for(j = j-1; arr[j] > key; j--);		/* the loop must terminate with j >= (i-1) as arr[i-1] <= key */
   
   		if(j <= i)	/* end of partition */
   		{
   			swap(arr, left, j);
   			break;
   		}
   		swap(arr, i, j);
   	}
   
   	return j;
   }
   
   void insertion_sort(int arr[], int left, int right)
   {
   	int i, min;
   
   	/* move smallest key to left end */
   	for(i = left+1, min = left; i <= right; i++)
   		if(arr[min] > arr[i])
   			min = i;
   
   	swap(arr, left, min);
   
   	for(i = left+1; i <= right; i++)
   	{
   		int j, key;
   
   		for(j = i-1, key = arr[i]; arr[j] > key; j--)
   				arr[j+1] = arr[j];
   
   		arr[j+1] = key;
   	}
   }
   
   static void swap(int arr[], int i, int j)
   {
   	int t;
   	t = arr[i];
   	arr[i] = arr[j];
   	arr[j] = t;
   }