Sorting is the process of assigning the elements of a collection (e.g. list) in a particular order (e.g. put words in an alphabetical order).
A simplistic systematic way to sort the elements of a collection is, first, to compare two values from the collection seeing which is the smaller (or greater).
And, second, if the two values are not in the correct order, based on their comparison, we need to exchange them.
This exchange is expensive and, therefore, the total number of the needed exchanges will indicate the efficiency of a sorting algorithm.
Example:
A simple sort algorithm where list elements “bubbles” to the position in the list where it belongs (e.g holding the order invariant)
Given a list \(C[]\) with \(n\) elements
Sort the following list \(C = [7,6,1]\)
This would require 2 comparisons for a list of 3 values
First iteration
Second iteration
Third iteration
Values are in order
Sort the following list \(C = [5,3,1,9,8,2,4,7]\) using bubble sort
def bubble_sort(list):
n_times = len(list)
# Traverse all list elements
for i in range(n_times):
print "round: " + str(i) + " with " + str(list)
for j in range(0, n_times-i-1):
# traverse the list from 0 to n-i-1 (e.g number of possible swap left)
print str(list[j]) + " > " + str(list[j+1]) + "?"
if list[j] > list[j+1] :
list[j], list[j+1] = list[j+1], list[j]
print "swap"
else:
print "no swap"
return list
For each iteration of loop variable \(i\), there are \(n-i\) comparisons performed. Thus, Bubble sort conducts \(O(n)\) operations on an \(O(n)\) number of elements that leads to a time complexity of \(O(n^2)\)
What about best case scenario?
Therefore, when \(i = n\), \(n - 1\) comparisons are performed irrespective of the input
For a list with \(n\) elements does:
\(1 + 2 + 3 + 4 + \cdots + (n - 2) + (n - 1) = O(n^2)\) comparisons
Last, the space complexity is \(O(1)\) (e.g constant amount of memory)
key idea: Search and swap algorithm
Sort the following list \(C = [-1,5,3,9,12,4,8]\)
def selectionSort(list):
for i in range(len(list)-1):
print "index " + str(i) + " in the list"
min = i
for j in range(i + 1, len(list)):
if list[j] < list[min]:
min = j
print "min value is " + str(list[min]) + " at index " + str(min)
list[i], list[min] = list[min], list[i]
return list
The selection sort makes the same number of comparisons as the bubble sort and is therefore also \(O(n^2)\). This is due to the linear search for finding the minimum element in which we have to pass \(i - n\) values
However, due to the reduction in the number of exchanges, the selection sort typically executes faster than the bubble sort.
What is the best case?
A simple sorting algorithm that works in similar fashion to sorting cards with our hands