Sort algorithms

Sort makes searches faster. Let’s cover famous sorting algorithms with their complexity and implementation. Implementation can vary a little, but the complexity in big O won’t vary.

Evaluation of sort algorithms

• Number of comparison
• Number of moves

Selection sort

Scan the unsorted numbers in an array to find the minimum number, then exchange this element with the first element of the unsorted numbers. Iterate this process until all elements are sorted.

def selection_sort(arr):
    compare=0
    move=0
    for i in range(len(arr)-1):
        idx=i
        for j in range(i+1,len(arr)):
            
            # search for the minimum
            compare+=1
            if arr[j] < arr[idx]:
                idx=j
                
        
        temp = arr[i]
        arr[i] = arr[idx]
        arr[idx] = temp
        move+=3
    return arr, compare, move
    
print(selection_sort([1,2,3,4,5]))
print(selection_sort([2,5,8,3,6,4,1,7]))
print(selection_sort([10,9,8,7,6,5,4,3,2,1]))

Output:

([1, 2, 3, 4, 5], 10, 12)
([1, 2, 3, 4, 5, 6, 7, 8], 28, 21)
([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 45, 27)

• Time complexity: O(n^2)
  • Number of comparison: (n-1)+(n-2)+…+1 = n(n-1)/2
  • Number of moves: 3(n-1)

Bubble sort

Compare two adjacent elements then sort these two. Iterate this process side by side until the end of the array, then iterate again from the beginning until all elements are sorted.

def bubble_sort(arr):
    comp=0
    move=0
    for i in range(len(arr)-1):
        for j in range(0,len(arr)-1-i):
            
            # compare with the +1 index array
            comp+=1
            if arr[j] > arr[j+1]:  
                temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
                move+=3
    return arr, comp, move

print(bubble_sort([1,2,3,4,5]))
print(bubble_sort([2,5,8,3,6,4,1,7]))
print(bubble_sort([10,9,8,7,6,5,4,3,2,1]))

Output:

([1, 2, 3, 4, 5], 10, 0)
([1, 2, 3, 4, 5, 6, 7, 8], 28, 39)
([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 45, 135)

• Time complexity: O(n^2)
  • Number of comparison: (n-1)+(n-2)+…+1 = n(n-1)/2
  • Number of moves
    • Best case: 0, when already sorted
    • Worst case: 3n(n-1)/2, when sorted in descending order

Insertion sort

Compare the i-th element with the sorted (i-1) to 0th elements, until finding a smaller element than i-th. Then put the i-th element behind that element.

def insertion_sort(arr):
    compare0=0
    compare1=0
    move0=0
    move1=0
    move2=0
    for i in range(1, len(arr)):
        temp = arr[i]
        move0+=1
        j=i-1
        
        compare0+=2
        while((arr[j]>temp) and (j>=0)):
            compare1+=2
            arr[j+1] = arr[j]
            move1+=1
            j-=1
            
        arr[j+1] = temp   
        move2+=1

    return arr, compare0, compare1, move0, move1, move2, compare0+compare1, move0+move1+move2

print(insertion_sort([1,2,3,4,5]))
print(insertion_sort([2,5,8,3,6,4,1,7]))
print(insertion_sort([10,9,8,7,6,5,4,3,2,1]))

Output:

([1, 2, 3, 4, 5], 8, 0, 4, 0, 4, 8, 8)
([1, 2, 3, 4, 5, 6, 7, 8], 14, 26, 7, 13, 7, 40, 27)
([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 18, 90, 9, 45, 9, 108, 63)

• Time complexity: O(n^2)
  • Number of comparison
    • Best case: 2(n-1), when already sorted
    • Worst case: 2(n-1)+n(n-1), when sorted in descending order
  • Number of moves
    • Best case: 2(n-1), when already sorted
    • Worst case: 2(n-1)+n(n-1)/2, when sorted in descending order

Note that the time complexity becomes O(n) when inserting a new element to a sorted array.

Quick sort

Set the most left element as the pivot, put the rest of the smaller (larger) elements on its left (right), then iterate this process for the two segments, one on the left of the pivot and the other on the right of the pivot.

def partition(arr, left, right):
    pivot = arr[left]
    low = left+1
    high = right
    
    while(low<=high):
        try:
            while((pivot > arr[low])&(low<=right)):
                low+=1
        except:
            pass
        try:
            while((pivot < arr[high])&(high>=(left+1))):
                high-=1
        except:
            pass
        if low<=high:
            temp=arr[low]
            arr[low]=arr[high]
            arr[high]=temp
    # now low>high
    temp=arr[left]
    arr[left]=arr[high]
    arr[high]=temp            
    return high

def quick_sort(arr, left, right):
    if left<=right:
        pivot = partition(arr, left, right)
        quick_sort(arr, left, pivot-1)
        quick_sort(arr,pivot+1, right)
        
    return arr
        
print(quick_sort([1,2,3,4,5],0,4))
print(quick_sort([2,5,8,3,6,4,1,7],0,7))
print(quick_sort([10,9,8,7,6,5,4,3,2,1],0,9))

Output:

[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

• Time complexity
  • Number of comparison
    • Best case: O(nlog2(n)), when a pivot split the list to equal sizes each time
    • Worst case: O(n^2), when a pivot split the list very imbalanced (e.g. already sorted array)
  • Number of moves: smaller than the number of comparison