@fitzcn/

UnfitTremendousPython

Python

No description

fork
loading
Files
  • main.py
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#http://interactivepython.org/runestone/static/pythonds/SortSearch/TheQuickSort.html
def quickSort(items):
   return quickSortHelper(items,0,len(items)-1)

def quickSortHelper(items,first,last):
    if first<last:
        splitpoint = partition(items,first,last)        
        quickSortHelper(items,first,splitpoint-1)
        quickSortHelper(items,splitpoint+1,last)

def partition(items,first,last):
    pivotvalue = items[first]
    print("pivoting on " + str(items[first]))
    leftmark = first+1
    rightmark = last
    print("moving right from " + str(items[leftmark]) + ", left from " + str(items[rightmark]))
    print(items)
    done = False
    while not done:
        while leftmark <= rightmark and items[leftmark] <= pivotvalue:
            leftmark = leftmark + 1
        while items[rightmark] >= pivotvalue and rightmark >= leftmark:
            rightmark = rightmark -1
        if rightmark < leftmark:
            done = True
        else:
            print("swapping " + str(items[leftmark]) + " with " + str((items[rightmark])))
            temp = items[leftmark]
            items[leftmark] = items[rightmark]
            items[rightmark] = temp
            print(items)

    temp = items[first] 
    items[first] = items[rightmark]
    items[rightmark] = temp
    return rightmark

#initialize a list of something, sort it, and print it
numbers = [54,26,93,17,77,31,44,55,20]
quickSort(numbers)
print(numbers)

###PSEUDOCODE###
#Choose a pivot value.
#Partition the array (put all value less than the pivot in the left part of the array, then the pivot itself, then all values greater than the pivot). Copies of the pivot value can go in either part of the array.
#Recursively, sort the values less (or equal to) than the pivot.
#Recursively, sort the values greater than (or equal to) the pivot