June 2, 2017 Omer Ramić Education

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)

• 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 <= right_half:             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 >= right_half:             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)```