Summary of five Sorting algorithms

Bubble Sort

The bubble sort makes multiple passes through a list. It compares adjacent items and exchanges those that are out of order. Each pass through the list places the next largest value in its proper place. In essence, each item “bubbles” up to the location where it belongs.

def BubbleSort(list):
    exchange=0
    comparison=0
    for i in range(len(list)-1,0,-1):
             for j in range(i):
                if list[j]>list[j+1]:
                    comparison=comparison+1
                    temp=list[j+1]
                    list[j+1]=list[j]
                    list[j]=temp
                    exchange=exchange+1
                else:
                    comparison=comparison+1
    return list,comparison,exchange
print(BubbleSort([54,26,93,17,77,31,15,8,63,31,44,55,20]))

([8, 15, 17, 20, 26, 31, 31, 44, 54, 55, 63, 77, 93], 78, 43)

Selection Sort

The selection sort improves on the bubble sort by making only one exchange for every pass through the list. In order to do this, a selection sort looks for the largest value as it makes a pass and, after completing the pass, places it in the proper location. As with a bubble sort, after the first pass, the largest item is in the correct place. After the second pass, the next largest is in place. This process continues and requires n−1 passes to sort n items, since the final item must be in place after the (n−1) st pass.

def SelectionSort(list):
    exchange=0
    comparison=0
    for i in range(len(list)-1,0,-1):
             max=list[0]
             index=0
             for j in range(1,i+1):
                  if list[j]>max:
                        comparison=comparison+1
                        max=list[j]
                        index=j
                  else:
                        comparison=comparison+1
             temp=list[i]
             list[i]=list[index]
             list[index]=temp
             exchange=exchange+1
                
    return list,comparison,exchange
print(SelectionSort([54,26,93,17,77,31,15,8,63,31,44,55,20]))

([8, 15, 17, 20, 26, 31, 31, 44, 54, 55, 63, 77, 93], 78, 12)

Insertion Sort

The insertion sort, although still O(n2), works in a slightly different way. It always maintains a sorted sublist in the lower positions of the list. Each new item is then “inserted” back into the previous sublist such that the sorted sublist is one item larger

def InsertionSort(list):
    exchange=0
    comparison=0
    for i in range(1,len(list)):
             value=list[i]
             index=i
             while index>0 and value<=list[index-1]:
                        list[index]=list[index-1]
                        index=index-1
                        comparison=comparison+1
                        exchange=exchange+1
             list[index]=value
             
                
    return list,comparison,exchange
print(InsertionSort([54,26,93,17,77,31,15,8,63,31,44,55,20]))

([8, 15, 17, 20, 26, 31, 31, 44, 54, 55, 63, 77, 93], 44, 44)

Shell Sort

The shell sort, sometimes called the “diminishing increment sort,” improves on the insertion sort by breaking the original list into a number of smaller sublists, each of which is sorted using an insertion sort. The unique way that these sublists are chosen is the key to the shell sort. Instead of breaking the list into sublists of contiguous items, the shell sort uses an increment i, sometimes called the gap, to create a sublist by choosing all items that are i items apart.

def gapinsertionsort(nums,start,gap):
             for i in range(start+gap,len(nums),gap):
                         value=nums[i]
                         index=i
                         while index>=gap and value<nums[index-gap]:
                                    nums[index]=nums[index-gap]
                                    index=index-gap
                         nums[index]=value
             return nums
                        
def ShellSort(list):
    count=len(list)//3
    while count>0 :
        for position in range(count):
               list=gapinsertionsort(list,position,count)
        print(count,list)
        count=count//3
        
    return list
print(ShellSort([54,26,93,17,77,31,15,8,63,31,44,55,20]))

4 [20, 26, 15, 8, 54, 31, 44, 17, 63, 31, 93, 55, 77]
1 [8, 15, 17, 20, 26, 31, 31, 44, 54, 55, 63, 77, 93]
[8, 15, 17, 20, 26, 31, 31, 44, 54, 55, 63, 77, 93]

Merge Sort

Merge sort is a recursive algorithm that continually splits a list in half. If the list is empty or has one item, it is sorted by definition (the base case). If the list has more than one item, we split the list and recursively invoke a merge sort on both halves. Once the two halves are sorted, the fundamental operation, called a merge, is performed. Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list.

def MergeSort(list):
    
    if len(list)>1:
        point=len(list)//2
        left=list[:point]
        right=list[point:]
        MergeSort(left)
        MergeSort(right)
        
        L=0
        R=0
        k=0
        while L<len(left) and R<len(right):
                    if left[L]<right[R]:
                        list[k]=left[L]
                        L=L+1
                        k=k+1
                    else:
                        list[k]=right[R]
                        R=R+1
                        k=k+1
        
        while L<len(left):
                        list[k]=left[L]
                        L=L+1
                        k=k+1
        
        while R<len(right):
                        list[k]=right[R]
                        R=R+1
                        k=k+1
    return list
print(MergeSort([54,26,93,17,77,31,15,8,63,31,44,55,20]))

[8, 15, 17, 20, 26, 31, 31, 44, 54, 55, 63, 77, 93]

Reference

Problem Solving with Algorithms and Data Structures Using Python. Bradley N. Miller, David L. Ranum. 2005