Sorting - A Quicksort Inplace algorithm in Python

Quicksort algorithm is an efficient (based on asymptotic complexity) algorithm for sorting. Some of the leading languages uses quicksort as its algorithm for sorting in their native libraries. In worse case it has BigO of n^2 and in average case it has a BigO of n log n . Before discussing about the in-place version lets see how its implemented without in-place rearrangements. Here is one such implementation below:

Asymptotic Complexity
Something	Time Complexity	Space Complexity
Worst Case Performance	O (n^2)
Best Case Performance	O (n log n )
Average Case Performance	O(n log n)
Worst Case space Complexity		O (log n) (for in-place)

	#! /usr/env/path python
	items = [2,5,6,7,8,5,0,1,2,3,4]
	def quick_sort(items):
	""" Implementation of quick sort """
	if len(items) > 1:
	pivot_index = len(items) // 2
	smaller_items = []
	larger_items = []
	for i, val in enumerate(items):
	if i != pivot_index:
	if val < items[pivot_index]:
	smaller_items.append(val)
	else:
	larger_items.append(val)
	quick_sort(smaller_items)
	quick_sort(larger_items)
	items[:] = smaller_items + [items[pivot_index]] + larger_items
	print(items)
	quick_sort(items)
	print(items)

view raw quicksort1.py hosted with ❤ by GitHub

The above algorithm uses two new arrays for its implementation and thereby does a bad job with regard to space complexity. Here is an inplace quicksort algorithm implementation in Python

If you are interested in a C implementation of the below algorithm see the following link: C implementation of inplace Quicksort.

	items = [2,5,6,7,8,5,0,1,9,3,4]
	#items = [3, 4, 5, 2 ,1]
	def quick_sort(items,first,last):
	""" Implementation of in-place quicksort """
	if(first < last):
	pivot, left, right = first, first, last
	while(left<right):
	while((left < last) and (items[left] <= items[pivot]) ):
	left +=1
	while((right > first) and (items[right] > items[pivot]) ):
	right-=1
	if(left<right):
	items[left] , items[right] = items[right] , items[left]
	left+=1
	right-=1
	items[pivot], items[right] = items[right],items[pivot]
	quick_sort(items, first , right-1)
	quick_sort(items, right+1, last)
	print ('----------------')
	print ('start %s' %items)
	print ('----------------')
	quick_sort(items,0,10)
	print ('----------------')
	print ('end %s' %items)
	print ('----------------')

view raw quicksort.py hosted with ❤ by GitHub