davegimo

Quicksort

Jan 23rd, 2021
627
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def partition(l, low, high):
  2.     pivot = l[high]
  3.     i = low - 1
  4.  
  5.     print(l)
  6.     print("pivot = " + str(pivot))
  7.  
  8.     for j in range(low, high):
  9.         if l[j] < pivot:
  10.             i += 1
  11.             swap(l, i, j)
  12.  
  13.         print("j = " + str(j) + ", i = " + str(i) )
  14.         print(l)
  15.  
  16.     i += 1
  17.     swap(l,i,high)
  18.     print("i = " + str(i))
  19.     print(l)
  20.     print()
  21.     return i
  22.  
  23.  
  24. def quicksort(l, low, high):
  25.  
  26.     if low < high:
  27.         pi = partition(l, low, high)
  28.         quicksort(l, low, pi - 1)  #lato sinistro della lista
  29.         quicksort(l, pi + 1, high) #lato destro della lista
  30.  
  31.  
  32. def swap(l,i,j):
  33.     temp = l[i]
  34.     l[i] = l[j]
  35.     l[j] = temp
  36.  
  37.  
  38. l = [9, 5, 1, 3, 8, 6, 4, 7]
  39. quicksort(l, 0, len(l) - 1)
  40.  
  41. print()
  42. print("lista ordinata L = " + str(l))
  43.  
  44.  
  45.  
RAW Paste Data