SHARE
TWEET

updated quicksort implementation

a guest Jul 21st, 2013 36 Never
  1. def qsort2(array):
  2.     try:
  3.         array,pI = partition(array)
  4.         return qsort2(array[:pI])+[array[pI]]+qsort2(array[pI+1:])
  5.     except:
  6.         return array
  7.  
  8. def partition(array):
  9.     print("before: ",array)
  10.     if len(array) > 1:
  11.         pivot = array[0]
  12.         pivIndex = 0
  13.         i,j = 1,1
  14.         while j < len(array) - 1:
  15.             if array[j] < pivot:
  16.                 temp = array[i]
  17.                 array[i] = array[j]
  18.                 array[j] = temp
  19.                 i += 1
  20.             j += 1
  21.         temp = array[i-1]
  22.         array[i-1] = array[pivIndex]
  23.         array[pivIndex] = temp
  24.         pivIndex = i-1
  25.         print("after",array)
  26.         return array,pivIndex
  27.     else:
  28.         print("after",array)
  29.         return array
  30.  
  31. print([3,8,2,5,1,4,7,6])
  32. print(qsort2([3,8,2,5,1,4,7,6]))
RAW Paste Data
Top