Skip to content

Instantly share code, notes, and snippets.

@lidio601
Last active August 29, 2015 14:27
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save lidio601/f4df4ac59e2fc485b037 to your computer and use it in GitHub Desktop.
Sample implementation of the Quick Sort algorithm ( O(N log(N)) order of complexity ) - Merge Sort variant
import random
__author__ = 'fabiocigliano'
def genarray():
n = int(random.random() * 10) + 1
ris = range(n)
random.shuffle(ris)
return ris
def scambia(array, i, j):
temp = array[i]
array[i] = array[j]
array[j] = temp
def quick_sort(a):
# recursion stop condition
if len(a) < 2:
return a
pivot = len(a)/2
# print "pivot", pivot, "=", a[pivot]
split1 = []
split2 = []
for i in range(len(a)):
if a[i] == a[pivot]:
continue
elif a[i] < a[pivot]:
split1.append(a[i])
else:
split2.append(a[i])
# print "before)", split1, [a[pivot]], split2
split1 = quick_sort(split1)
split2 = quick_sort(split2)
a = split1 + [a[pivot]] + split2
# print "after) ", split1, [a[pivot]], split2
return a
if __name__ == "__main__":
array = genarray()
print "test input array: ", array
array = quick_sort(array)
print "test output array:", array
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment