|
| 1 | +# Python program for implementation of Quicksort Sort |
| 2 | + |
| 3 | +# This function takes last element as pivot, places |
| 4 | +# the pivot element at its correct position in sorted |
| 5 | +# array, and places all smaller (smaller than pivot) |
| 6 | +# to left of pivot and all greater elements to right |
| 7 | +# of pivot |
| 8 | + |
| 9 | + |
| 10 | +def partition(arr, low, high): |
| 11 | + i = (low-1) # index of smaller element |
| 12 | + pivot = arr[high] # pivot |
| 13 | + |
| 14 | + for j in range(low, high): |
| 15 | + |
| 16 | + # If current element is smaller than or |
| 17 | + # equal to pivot |
| 18 | + if arr[j] <= pivot: |
| 19 | + |
| 20 | + # increment index of smaller element |
| 21 | + i = i+1 |
| 22 | + arr[i], arr[j] = arr[j], arr[i] |
| 23 | + |
| 24 | + arr[i+1], arr[high] = arr[high], arr[i+1] |
| 25 | + return (i+1) |
| 26 | + |
| 27 | +# The main function that implements QuickSort |
| 28 | +# arr[] --> Array to be sorted, |
| 29 | +# low --> Starting index, |
| 30 | +# high --> Ending index |
| 31 | + |
| 32 | +# Function to do Quick sort |
| 33 | + |
| 34 | + |
| 35 | +def quickSort(arr, low, high): |
| 36 | + if len(arr) == 1: |
| 37 | + return arr |
| 38 | + if low < high: |
| 39 | + |
| 40 | + # pi is partitioning index, arr[p] is now |
| 41 | + # at right place |
| 42 | + pi = partition(arr, low, high) |
| 43 | + |
| 44 | + # Separately sort elements before |
| 45 | + # partition and after partition |
| 46 | + quickSort(arr, low, pi-1) |
| 47 | + quickSort(arr, pi+1, high) |
| 48 | + |
| 49 | + |
| 50 | +# Driver code to test above |
| 51 | +arr = [10, 7, 8, 9, 1, 5] |
| 52 | +n = len(arr) |
| 53 | +quickSort(arr, 0, n-1) |
| 54 | +print("Sorted array is:") |
| 55 | +for i in range(n): |
| 56 | + print("%d" % arr[i]), |
| 57 | + |
| 58 | +# This code is contributed by Mohit Kumra |
| 59 | +#This code in improved by https://github.com/anushkrishnav |
0 commit comments