SHARE
TWEET

ducking quicksort

JSchmoe Mar 21st, 2016 94 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import random
  2.  
  3. def bubblesort(s):
  4.     tosort = list(s)
  5.     changes_made = False
  6.    
  7.     for x in range(len(tosort)):
  8.         for i, element in enumerate(tosort):
  9.             try:
  10.                 if tosort[i] > tosort[i+1]:
  11.                     tosort[i], tosort[i+1] = tosort[i+1], tosort[i]
  12.                     changes_made = True
  13.             except IndexError:
  14.                 continue
  15.         if not changes_made: return tosort
  16.         changes_made = False
  17.  
  18.    
  19. def bogosort(s):
  20.     tosort = list(s)
  21.    
  22.     while tosort != sorted(tosort):
  23.         random.shuffle(tosort)
  24.        
  25.     return tosort
  26.    
  27. def selectionsort(s):
  28.     tosort = list(s)
  29.    
  30.     for i in range(len(tosort)):
  31.         minimum = i
  32.        
  33.         for x in range(i+1,len(tosort)):
  34.             if tosort[x] < tosort[minimum]:
  35.                 minimum = x
  36.                
  37.         if minimum != i:
  38.             tosort[i], tosort[minimum] = tosort[minimum], tosort[i]
  39.            
  40.     return tosort
  41.    
  42. def insertsort(s):
  43.     tosort = list(s)
  44.     while tosort != sorted(tosort):
  45.         for i in range(1, len(tosort)):
  46.             if tosort[i-1] > tosort[i]:
  47.                 hold = tosort[i]
  48.                 pos = i
  49.                 while pos > 0:
  50.                     tosort[pos] = tosort[pos-1]
  51.                     pos -= 1
  52.                     if tosort[pos+1] <= hold: break
  53.                    
  54.                 tosort[pos] = hold
  55.                
  56.     return tosort
  57.    
  58. def quicksort(s, pivot_point):
  59.     tosort = list(s)
  60.     if len(tosort) <= 1: return tosort
  61.     pivot_char = tosort[pivot_point]
  62.     left = []
  63.     right = []
  64.    
  65.     for i in range(len(tosort)):
  66.         if i == pivot_point: next
  67.        
  68.         if tosort[i] < pivot_char:
  69.             left += tosort[i]
  70.         else:
  71.             right += tosort[i]
  72.            
  73.     if len(left) <= 1:
  74.         left = quicksort(left, 0)
  75.     else:
  76.         left = quicksort(left, random.randrange(0, len(left)))
  77.        
  78.     if len(right) <= 1:
  79.         right = quicksort(right, 0)
  80.     else:
  81.         right = quicksort(left, random.randrange(0, len(right)))
  82.    
  83.     sorted = left
  84.     sorted += pivot_char
  85.     sorted += right
  86.    
  87.     return sorted
  88.            
  89. s = raw_input("Please input string to be sorted: ")
  90. print("Bubble sort: "+str(bubblesort(s)))
  91. print("Insertion sort: "+str(insertsort(s)))
  92. print("Quicksort (fucked): "+str(quicksort(s, 2)))
  93. print("Selection sort: "+str(selectionsort(s)))
  94. print("Bogo: go away")
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