SHARE
TWEET

Untitled

xiaoxiang1225 Nov 14th, 2019 117 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import statistics
  2.  
  3.  
  4. def quickSort(alist):
  5.     quickSortHelper(alist, 0, len(alist) - 1)
  6.  
  7.  
  8. def quickSortHelper(alist, first, last):
  9.     if first < last:
  10.         splitpoint = partition(alist, first, last)
  11.  
  12.         quickSortHelper(alist, first, splitpoint - 1)
  13.         quickSortHelper(alist, splitpoint + 1, last)
  14.  
  15.  
  16. def partition(alist, first, last):
  17.     mid = (last - first) // 2
  18.     medianlist = [alist[first], alist[mid], alist[last]]
  19.     median = statistics.median(medianlist)
  20.  
  21.     if median == alist[mid]:
  22.         alist[first], alist[len(alist) // 2] = alist[len(alist) // 2], alist[first]
  23.     elif median == alist[last]:
  24.         alist[first], alist[last] = alist[last], alist[first]
  25.  
  26.     pivotvalue = alist[first]
  27.  
  28.     leftmark = first + 1
  29.     rightmark = last
  30.  
  31.     done = False
  32.     while not done:
  33.  
  34.         while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
  35.             leftmark = leftmark + 1
  36.  
  37.         while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
  38.             rightmark = rightmark - 1
  39.  
  40.         if rightmark < leftmark:
  41.             done = True
  42.         else:
  43.             temp = alist[leftmark]
  44.             alist[leftmark] = alist[rightmark]
  45.             alist[rightmark] = temp
  46.  
  47.     temp = alist[first]
  48.     alist[first] = alist[rightmark]
  49.     alist[rightmark] = temp
  50.  
  51.     return rightmark
  52.  
  53.  
  54. alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
  55. quickSort(alist)
  56. print(alist)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top