Sorting

The following examples show two implementations of a quicksort algorithm, one using the Lomot, one using the Horade partitioning approach, and one example for merge sort.



In [15]:

    
n = 5
e = 1
for i in range(1, n+1):
    e = e * i
#e

def fac(n):
    if n <= 1:
        return n
    return(n * fac(n-1))
    
d = fac(5)
print(d)

Quicksort with partition algorithm of Lomoto

Example following pseudocode taken from Wikipedia



In [23]:

    
def partitionLomoto(my_list, low, high):
    pivot = my_list[high]
    print("Actual pivot", pivot)
    print("Actual list before partitioning", my_list[low:high+1])
    i = low
    for j in range(low, high):
        if my_list[j] <= pivot:
            my_list[i], my_list[j] = my_list[j], my_list[i]
            i = i+1
    my_list[i], my_list[high] = my_list[high], my_list[i]
    pivot = i
    print("Actual list after partitioning", my_list[low:high+1])
    print("New pivot position: ", pivot)
    print("------------------")
    return pivot

def quickSortLomoto(my_list, low, high):
    if low < high:
        pivot = partitionLomoto(my_list, low, high)
        quickSortLomoto(my_list, low, pivot-1)
        quickSortLomoto(my_list, pivot+1, high)
    return my_list



In [24]:

    
my_unsorted_list = [21,11,31,9,8,19,1]
my_list = my_unsorted_list
quickSortLomoto(my_unsorted_list, 0, len(my_unsorted_list)-1)









    



Actual pivot 1
Actual list before partitioning [21, 11, 31, 9, 8, 19, 1]
Actual list after partitioning [1, 11, 31, 9, 8, 19, 21]
New pivot position:  0
------------------
Actual pivot 21
Actual list before partitioning [11, 31, 9, 8, 19, 21]
Actual list after partitioning [11, 9, 8, 19, 21, 31]
New pivot position:  5
------------------
Actual pivot 19
Actual list before partitioning [11, 9, 8, 19]
Actual list after partitioning [11, 9, 8, 19]
New pivot position:  4
------------------
Actual pivot 8
Actual list before partitioning [11, 9, 8]
Actual list after partitioning [8, 9, 11]
New pivot position:  1
------------------
Actual pivot 11
Actual list before partitioning [9, 11]
Actual list after partitioning [9, 11]
New pivot position:  3
------------------






    Out[24]:





[1, 8, 9, 11, 19, 21, 31]

Quicksort with partition algorithm of Hoare

Example following pseudocode taken from Wikipedia



In [16]:

    
def partitionHoare(my_list, low, high):
    pivot = my_list[low]
    print("Actual pivot", pivot)
    print("Actual list before partitioning", my_list[low:high])
    i = low
    j = high
    
    while True:
        while my_list[i] < pivot:
            i = i + 1
            print(i)
        while my_list[j] > pivot:
            j = j - 1
            print(j)
        if i >= j:
            print("Actual list after partitioning", my_list[low:high])
            print("New pivot position: ", pivot)
            print("------------------")
            return j
        else:
            my_list[i], my_list[j] = my_list[j], my_list[i]
    return pivot

def quickSortHoare(my_list, low, high):
    if low < high:
        pivot = partitionHoare(my_list, low, high)
        quickSortHoare(my_list, low, pivot)
        quickSortHoare(my_list, pivot+1, high)
    return my_list



In [20]:

    
my_unsorted_list = [21,11,31,9, 25, 8,19,1]
my_list = my_unsorted_list
quickSortHoare(my_unsorted_list, 0, len(my_unsorted_list)-1)









    



Actual pivot 21
Actual list before partitioning [21, 11, 31, 9, 25, 8, 19]
1
2
6
3
4
5
5
Actual list after partitioning [1, 11, 19, 9, 8, 21, 25]
New pivot position:  21
------------------
Actual pivot 1
Actual list before partitioning [1, 11, 19, 9, 8]
4
3
2
1
0
Actual list after partitioning [1, 11, 19, 9, 8]
New pivot position:  1
------------------
Actual pivot 11
Actual list before partitioning [11, 19, 9, 8]
4
2
3
3
Actual list after partitioning [8, 9, 11, 19]
New pivot position:  11
------------------
Actual pivot 8
Actual list before partitioning [8, 9]
2
1
Actual list after partitioning [8, 9]
New pivot position:  8
------------------
Actual pivot 9
Actual list before partitioning [9]
2
Actual list after partitioning [9]
New pivot position:  9
------------------
Actual pivot 19
Actual list before partitioning [19]
4
Actual list after partitioning [19]
New pivot position:  19
------------------
Actual pivot 25
Actual list before partitioning [25]
6
Actual list after partitioning [25]
New pivot position:  25
------------------






    Out[20]:





[1, 8, 9, 11, 19, 21, 25, 31]

Merge sort

Example following pseudocode taken from Wikipedia



In [1]:

    
def mergeSort(my_list):
    if len(my_list) <= 1:
        return my_list

    half = len(my_list)//2
    left_list = my_list[:half]
    right_list = my_list[half:]
    print("Left list :", left_list, "Right list :", right_list)

    left_list = mergeSort(left_list)
    right_list = mergeSort(right_list)
    
    return merge(left_list, right_list)

def merge(left_list, right_list):
    print("Merging...")
    result = []
    while len(left_list) > 0 and len(right_list) > 0:
        if left_list[0] < right_list[0]:
            print("Left :", left_list[0], "Right :", right_list[0])
            result.append(left_list.pop(0))
            print("Result :", result)
        else:
            print("Left :", left_list[0], "Right :", right_list[0])
            result.append(right_list.pop(0))
            print("Result :", result)
    while len(left_list) > 0:
        print("Left :", left_list[0])
        result.append(left_list.pop(0))
        print("Result :", result)
    while len(right_list) > 0:
        print("Right :", right_list[0])
        result.append(right_list.pop(0))
        print("Result :", result)
    print("------------------")
    return result

alist = [54,26,93,17,77,31,44,55,20]
sort = mergeSort(alist)
print(sort)









    



Left list : [54, 26, 93, 17] Right list : [77, 31, 44, 55, 20]
Left list : [54, 26] Right list : [93, 17]
Left list : [54] Right list : [26]
Merging...
Left : 54 Right : 26
Result : [26]
Left : 54
Result : [26, 54]
------------------
Left list : [93] Right list : [17]
Merging...
Left : 93 Right : 17
Result : [17]
Left : 93
Result : [17, 93]
------------------
Merging...
Left : 26 Right : 17
Result : [17]
Left : 26 Right : 93
Result : [17, 26]
Left : 54 Right : 93
Result : [17, 26, 54]
Right : 93
Result : [17, 26, 54, 93]
------------------
Left list : [77, 31] Right list : [44, 55, 20]
Left list : [77] Right list : [31]
Merging...
Left : 77 Right : 31
Result : [31]
Left : 77
Result : [31, 77]
------------------
Left list : [44] Right list : [55, 20]
Left list : [55] Right list : [20]
Merging...
Left : 55 Right : 20
Result : [20]
Left : 55
Result : [20, 55]
------------------
Merging...
Left : 44 Right : 20
Result : [20]
Left : 44 Right : 55
Result : [20, 44]
Right : 55
Result : [20, 44, 55]
------------------
Merging...
Left : 31 Right : 20
Result : [20]
Left : 31 Right : 44
Result : [20, 31]
Left : 77 Right : 44
Result : [20, 31, 44]
Left : 77 Right : 55
Result : [20, 31, 44, 55]
Left : 77
Result : [20, 31, 44, 55, 77]
------------------
Merging...
Left : 17 Right : 20
Result : [17]
Left : 26 Right : 20
Result : [17, 20]
Left : 26 Right : 31
Result : [17, 20, 26]
Left : 54 Right : 31
Result : [17, 20, 26, 31]
Left : 54 Right : 44
Result : [17, 20, 26, 31, 44]
Left : 54 Right : 55
Result : [17, 20, 26, 31, 44, 54]
Left : 93 Right : 55
Result : [17, 20, 26, 31, 44, 54, 55]
Left : 93 Right : 77
Result : [17, 20, 26, 31, 44, 54, 55, 77]
Left : 93
Result : [17, 20, 26, 31, 44, 54, 55, 77, 93]
------------------
[17, 20, 26, 31, 44, 54, 55, 77, 93]