Sorting in python
What’s sorting?
Sorting is nothing but arranging the items in a particular sequence. In other words, sorting is the ordering of elements based on our preference. Preference can be ascending or descending depending on our requirements.
In this article, we are going to discuss two sorting algorithms and their differences.
- Insertion sort
- Merge sort
Insertion sort
Consider a list of elements
x = [73, 79, 56, 4, 48, 35]Implementation strategy for ascending order
Step 1:
key_element = x[key]x[:key] is the list that contains all the elements before the key elementx[:key] is sorted
Step 2:
if some of the elements in x[:key] is greater than x[key]do pairwise swaps until all the elements in the x[:key+1] is sorted
Step 3:
if all the elements in that x[:key+1] is sorted then move the key to the next index until there's no index leftImplementation of the example
key = 0key_element = 73arr_left = x[:key] = []
No elements to the left of the key.
No comparisons.
No pairwise swaps required.
Move the key one step to the right
key = 1arr_left = [:key] = [73]key_element = x[key] = 79
compare 79 with the elements that are on the left
79 > 73
No pairwise swaps required.
Move the key one step to the right
key = 2key_element = 56arr_left = [73, 79]
Note that arr_left is sorted
Compare key element with the elements of arr_left from right to left
compare(56, 79)
56<79
swap(56, 79)
def swap(x,y):
temp = x
x = y
y = temp
return x,y
compare (56, 73)
56<73
swap(56, 73)
No more comparisons required.
Move the key to the right.
key = 3key_element = x[3] = 4arr_left = [56, 73, 79]
compare(4, 79)
4 < 79
swap(4, 79)
compare(4, 73)
4 < 73
swap(4,73)
compare(4, 56)
4< 56
swap(4, 56)
No more comparisons required.
No more swaps required.
Move the key to the right.
key = 4key_element = 48arr_left = [4,56,73,79]
compare(48, 79)
48 < 79
swap(48, 79)
compare(48, 73)
48 < 73
swap(48, 73)
compare(48, 56)
48 < 56
swap(48, 56)
compare(48, 4)
48 > 4
No swaps required.
The comparisons with arr_left end here since arr_left is sorted and so element before the element 4 is greater than 4
Move the key to the right
key = 5key_element = 35arr_left = [4, 48, 56, 73, 79]
compare(35, 79)
35 < 79
swap(35, 79)
compare(35, 73)
35 < 73
swap(35, 73)
compare(35, 56)
35 < 56
swap(35, 56)
compare(35, 48)
35 < 48
swap(35, 48)
compare(35, 4)
35 > 4
No swaps
The comparisons end here
Since there are no more elements to the right of the key. No more shifts to do
The implementation ends here
Final sorted list
Python Code
Time Complexity
number_of_keys = nnumber_of_swaps_for_each_key = n (in the worst case)total time required = n*n upper bound = O(n*n)
Merge Sort
Consider the same list of elements again
x = [73, 79, 56, 4, 48, 35]Implementation Strategy
Process : Divide the list into two halfs sort the left half sort the right half Merge both the halfs
Repeat this process as much as possible
Implementation example
Merging two sub halves
For example, consider [73, 79, 56] and [4, 48, 35]
def merge(arr1, arr2):
i = 0 j = 0
result = [] while(i< len(arr1) or j< len(arr2)): if(i< len(arr1) and j< len(arr2)): if(arr1[i] > arr2[j]): result.append(arr2[j]) j = j + 1 else: result.append(arr1[i]) i = i + 1 elif(i< len(arr1) and j == len(arr2)): result.append(arr1[i]) i = i + 1 else: result.append(arr2[j]) j = j + 1
return result
In this way, we recursively merge all the sub halves we generated
That will give us the sorted array
This is a divide and conquers approach
Python code
The time complexity of this algorithm
Number of divisions = lognTime to merge two sub halves (at the worst case) : nTotal time = logn * nUpper bound time = O(n*logn)
Let’s compare both sorting algorithms with a large set of numbers
Consider a list of 10000 numbers
Check the time taken to sort this list of numbers using both sorting techniques
Merge sort is performing a lot faster compared to the insertion sort.
