Guest User

Untitled

a guest
Dec 9th, 2019
124
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. def partition(arr,low,high):
  9.     i = ( low-1 )        # index of smaller element
  10.     pivot = arr[high]    # pivot
  11.  
  12.     for j in range(low , high):
  13.  
  14.         # If current element is smaller than or
  15.         # equal to pivot
  16.         if arr[j] <= pivot:
  17.        
  18.             # increment index of smaller element
  19.             i = i+1
  20.             arr[i],arr[j] = arr[j],arr[i]
  21.  
  22.     arr[i+1],arr[high] = arr[high],arr[i+1]
  23.     return ( i+1 )
  24.  
  25. # The main function that implements QuickSort
  26. # arr[] --> Array to be sorted,
  27. # low --> Starting index,
  28. # high --> Ending index
  29.  
  30. # Function to do Quick sort
  31. def quickSort(arr,low,high):
  32.     if low < high:
  33.  
  34.         # pi is partitioning index, arr[p] is now
  35.         # at right place
  36.         pi = partition(arr,low,high)
  37.  
  38.         # Separately sort elements before
  39.         # partition and after partition
  40.         quickSort(arr, low, pi-1)
  41.         quickSort(arr, pi+1, high)
  42.  
  43. # Driver code to test above
  44. arr = [10, 7, 8, 9, 1, 5]
  45. n = len(arr)
  46. quickSort(arr,0,n-1)
  47. print ("Sorted array is:")
  48. for i in range(n):
  49.     print ("%d" %arr[i]),
  50.  
  51. # This code is contributed by Mohit Kumra
RAW Paste Data