June 2, 2017 Omer Ramić Education
Simple time efficiency comparison of sorting algorithms in Python

Benchmark for time efficiency of sorting algorithms in python.

I have made a list comprised of 7000 randomly generated elements between '0' and '9999'. Than I have defined sorting functions which take the generated list as the input parameter. After functions are called and finnished I got time outputs as seen in listing bellow for each sorting algorithm. We see that Quick Sort was the most efficient. Quick sort took only 30 miliseconds to sort this huge list.

5.9300 seconds for BubbleSortAsc
5.6220 seconds for BubbleSortDsc
1.6525 seconds for SelectionSortAsc
1.6672 seconds for SelectionSortDsc
4.0712 seconds for InsertionSortAsc
4.0218 seconds for InsertionSortDsc
2.4006 seconds for ShellSortAsc
2.3620 seconds for ShellSortDsc
0.0557 seconds for MergeSortAsc
0.0505 seconds for MergeSortDsc
0.0329 seconds for QuickSortAsc
0.0306 seconds for QuickSortDsc

1. Sorting by swapping list elements had the worst times

This kind of sorting is done by comparing each list pair of adjacent items and swapping them. This is the simplest way to sort the list. These algorithms that compare each pair inside the list are:

  • Bubble sort (sorting by substituting adjacent elements)
  • Selection sort (sorting by selecting the smallest element)

#Bubble sort algorithm ascending - python code
#by Omer Ramić
def BubbleSortAsc(lst):
    swapped = True
    sortedvalue=0
    while swapped:
        swapped = False
        sortedvalue+=1
        for i in range(0,len(lst)-sortedvalue):
            if lst[i]>lst[i+1]:
                lst[i], lst[i+1], swapped = lst[i+1], lst[i], True

#Bubble sort algorithm descending - python code
#by Omer Ramić
def BubbleSortDsc(lst):
    swapped = True
    sortedvalue=0
    while swapped:
        swapped = False
        sortedvalue+=1
        for i in range (0,len(lst)-sortedvalue):
            if lst[i]<lst[i+1]:
                lst[i], lst[i+1], swapped = lst[i+1], lst[i], True

#Selection sort algorithm ascending - python code
#by Omer Ramić
def SelectionSortAsc(lst):
    swapped = True
    counter=0
    while swapped:
        swapped = False
        min=lst[counter]
        for i in range (counter,len(lst)):
            if min>=lst[i]:
                min=lst[i]
                index=i
                swapped = True
        lst[counter], lst[index] = lst[index], lst[counter]
        counter+=1
        if counter==len(lst): break

#Selection sort algorithm descending - python code
#by Omer Ramić
def SelectionSortDsc(lst):
    swapped = True
    counter=0
    while swapped:
        swapped = False
        min=lst[counter]
        for i in range (counter,len(lst)):
            if min<=lst[i]:
                min=lst[i]
                index=i
                swapped = True
        lst[counter], lst[index] = lst[index], lst[counter]
        counter+=1
        if counter==len(lst): break

2. Sorting by inserting elements

These sort algorithms are based on logic which requires you to insert an element to already sorted part of the list. Examples for this sort algorithms are:

  • Insertion sort (simple sorting by inserting)
  • Shell sort (multiple sorting by inserting)

#Insertion sort algorithm ascending - python code
#by Omer Ramić
def InsertionSortAsc(lst):
    counter=0
    while counter<len(lst)-1:
        for i in range(counter+1,0,-1):
            if lst[i]<lst[i-1]:
                lst[i], lst[i-1] = lst[i-1], lst[i]
            else: break
        counter+=1

#Insertion sort algorithm descending - python code
#by Omer Ramić
def InsertionSortDsc(lst):
    counter=0
    while counter<len(lst)-1:
        for i in range(counter+1,0,-1):
            if lst[i]>lst[i-1]:
                lst[i], lst[i-1] = lst[i-1], lst[i]
            else: break
        counter+=1

#Shell sort algorithm ascending - python code
#by Omer Ramić
def ShellSortAsc(lst):
    gap=len(lst)//2
    while gap>0:
        for i in range(0, len(lst)-gap):
            if lst[i]>lst[i+gap]:
                lst[i], lst[i+gap] = lst[i+gap], lst[i]
                for j in range(i-gap,-1,-gap):
                    if lst[j]>lst[j+gap]:
                        lst[j], lst[j+gap] = lst[j+gap], lst[j]
        gap//=2

#Shell sort algorithm descending - python code
#by Omer Ramić
def ShellSortDsc(lst):
    gap=len(lst)//2
    while gap>0:
        for i in range(0, len(lst)-gap):
            if lst[i]<lst[i+gap]:
                lst[i], lst[i+gap] = lst[i+gap], lst[i]
                for j in range(i-gap,-1,-gap):
                    if lst[j]<lst[j+gap]:
                        lst[j], lst[j+gap] = lst[j+gap], lst[j]
        gap//=2

3. Recursive sorting - divide and conquer

Recursive algorithms are those algorithms whose functions call itself. In this group of algorithms we have Merge sort and Quick sort.
Merge sort (sorting by merging)

  • additional memory needed
  • every iteration creates new list, these lists are merged after sorting is done

Quick sort (quick sorting)

  • additional memory is not needed
  • list elements are sorted directly inside the forwarded list

#Merge sort algorithm ascending - python code
#by Omer Ramić
def MergeSortAsc(lst):
    half = len(lst)//2
    left_half, right_half = lst[:half], lst[half:]
    if len(left_half) > 1: left_half = MergeSortAsc(left_half)
    if len(right_half)> 1: right_half= MergeSortAsc(right_half)
    sorted_list = []
    while left_half and right_half:
        if left_half[0] <= right_half[0]:
            sorted_list.append(left_half.pop(0))
        else:
            sorted_list.append(right_half.pop(0))
    return sorted_list + (left_half or right_half)

#Merge sort algorithm descending - python code
#by Omer Ramić
def MergeSortDsc(lst):
    half = len(lst)//2
    left_half, right_half = lst[:half], lst[half:]
    if len(left_half) > 1: left_half = MergeSortDsc(left_half)
    if len(right_half)> 1: right_half= MergeSortDsc(right_half)
    sorted_list = []
    while left_half and right_half:
        if left_half[0] >= right_half[0]:
            sorted_list.append(left_half.pop(0))
        else:
            sorted_list.append(right_half.pop(0))
    return sorted_list + (left_half or right_half)

#Quick sort algorithm ascending - python code
#by Omer Ramić
def QuickSortAsc(lst,pivot,high):
    index=pivot+1
    if index>high: return
    border=pivot
    while index<=high:
        if lst[index]<=lst[pivot]:
            border+=1
            lst[index], lst[border] = lst[border], lst[index]
        index+=1
    if lst[pivot]>lst[border]:
        lst[pivot], lst[border] = lst[border], lst[pivot]
    QuickSortAsc(lst,pivot,border-1)
    QuickSortAsc(lst,border+1,index-1)

#Quick sort algorithm descending - python code
#by Omer Ramić
def QuickSortDsc(lst,pivot,high):
    index=pivot+1
    if index>high: return
    border=pivot
    while index<=high:
        if lst[index]>=lst[pivot]:
            border+=1
            lst[index], lst[border] = lst[border], lst[index]
        index+=1
    if lst[pivot]<lst[border]:
        lst[pivot], lst[border] = lst[border], lst[pivot]
    QuickSortDsc(lst,pivot,border-1)
    QuickSortDsc(lst,border+1,index-1)