Quick Sort in Python
Overview
Quick sort algorithm also costs O(n*n) time complexity.
It uses a divide and conquer approach – it keeps partitioning
and sorting those partitions until done.
Here is an implementation in Python.
Note: If you really want to sort you can use python std library or
even other libraries implementing better algorithms. This is just to
illustrate how to implement a simple algorithm in Python.
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#!/bin/python3 def quick_sort(array, startIndex, endIndex): if startIndex < endIndex: middle = partition(array, startIndex, endIndex) quick_sort(array, startIndex, middle - 1) quick_sort(array, middle + 1, endIndex) return array def partition(array, startIndex, endIndex): pivot = startIndex + (endIndex - startIndex) // 2; pivotIndex = startIndex array[pivot], array[endIndex] = array[endIndex], array[pivot] for i in range(startIndex, endIndex): if array[i] < array[endIndex]: array[pivotIndex], array[i] = array[i], array[pivotIndex] pivotIndex += 1 array[endIndex], array[pivotIndex] = array[pivotIndex], array[endIndex] return pivotIndex if __name__ == '__main__': print("Enter numbers separated by space: ") numbers = [ int(i) for i in input().rstrip().split() ] print("Quick Sort Result: ", quick_sort(numbers, 0, len(numbers)-1)) |
