QuickSort in Python

Just thought I’d post this little snippet to illustrate the facility with which array and list functions can be performed in Python, as opposed to classical languages like C++

 

Here’s a QuickSort implementation in C++, I’m not saying it’s the best, but hell it’s a QuickSort.


/*	Function for partitioning the array		*/
int Partition(int low, int high, int arr[])
{
	int i, high_vac, low_vac, pivot;
	pivot = arr[low];
	while(high > low)
	{
		high_vac=arr[high];
		while(pivot<high_vac)
		{
			if(high<=low) break;
			high--;
			high_vac=arr[high];
		}

		arr[low]=high_vac;
		low_vac=arr[low];
		while(pivot>low_vac)
		{
			if(high<=low) break;
			low++;
			low_vac=arr[low];
		}
		arr[high]=low_vac;
	}
	arr[low]=pivot;
	return low;
}

/*	Canonical QuickSort method */
void QuickSort(int low, int high, int arr[])
{
	int Piv_index,i;
	if(low < high)
	{
		Piv_index = Partition(low,high,arr);
		QuickSort(low,Piv_index-1,arr);
		QuickSort(Piv_index+1,high,arr);
	}
}

Now look at the same in Python:

def QuickSort(list):
    if list == []: 
        return []
    else:
        pivot = list[0]
        lesser = [x for x in list[1:] if x < pivot]
        greater = [x for x in list[1:] if x >= pivot]
        return QuickSort(lesser) + [pivot] + QuickSort(greater)
    
        

I mean, performance aside, this is a really compelling illustration, for me, of Python’s power and expressiveness.

Advertisements

About this entry