5 Sorting Algorithms And How They Work
First, What an Algorithm?
An algorithm is a step-to-step instruction on how to solve a particular problem.
Now, What is a Sorting Algorithm?
A Sorting Algorithm is used to rearrange a given array or list elements according to a
comparison operator on the elements. The comparison operator is used to decide the new
order of the element in the respective data structure.
Below are a few Sorting algorithms and How they work,
⭐ Bubble Sort Algorithm
It is one of the most simple sorting algorithms. The basic idea is it compares the adjacent elements and swaps their positions if they are not in the intended order. The order can be ascending or descending.
This is how it works,
Starting from the first index, we compare the first and second elements. If the first element is greater than the second element, we simply swap them. Next, compare the second and third element, we swap them if they are not in order. Repeat the above process until the last element.
Below is a simple example that illustrates how this algorithm works,
First Iteration:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, the algorithm compares the first two elements and
swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5),
the algorithm does not swap them.
Second Iteration:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Now, the list is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Iteration:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Below is the Python implementation of the Bubble Sort Algorithm,
def bubbleSort(list1):
for i in range(len(list1)):
for j in range(0, len(list1) - i - 1):
if list1[j] > list1[j + 1]:
(list1[j], list1[j + 1]) = (list1[j + 1], list1[j])
data = [25, 42, 10, 3, 6]
print(bubbleSort(data))
⭐ Selection Sort Algorithm
A bubble sort might be slow since it compares every single element and the swaps and
repeats the process, here comes Selection sort. In selection sort, the list is divided
into two parts, the sorted part at the left end and the unsorted part at the right end.
Initially, the sorted part is empty and the unsorted part is the entire list.
The smallest element is selected from the unsorted array and swapped with the leftmost
element, and that element becomes a part of the sorted array. This process continues
moving an unsorted array boundary by one element to the right.
Below is a simple example that illustrates how this algorithm works,
list = [58 21 16 28 13]
Find the minimum element in the list[0..4] and place it at the beginning
13 21 16 28 58
Find the minimum element in the list[1...4] and place it at the beginning of the
list[1...4]
13 16 28 21 64
Find the minimum element in the list[2...4] and place it at the beginning of the
list[2...4]
13 16 21 28 64
Find the minimum element in the list[3...4] and place it at the beginning of the
list[3...4]
11 12 22 25 64
Below is the Python implementation of the Selection Sort Algorithm,
def selectionSort(list1, size):
for step in range(size):
minIndex = step
for i in range(step + 1, size):
if list[i] < list[minIndex]:
min_idx = i
(list[step], list[minIndex]) = (list[minIndex], list[step])
list1 = [25, 42, 10, 3, 6]
size = len(list1)
print(selectionSort(list1, size))
⭐ Insertion Sort Algorithm
Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands. We assume that the first card is already sorted then, we select an unsorted card. If the unsorted card is greater than the card in hand, it is placed on the right otherwise, to the left. In the same way, other unsorted cards are taken and put in the right place. Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each iteration.
Below is a simple example that illustrates how this algorithm works,
12, 11, 13, 5, 6
Let us loop for i = 1 (second element of the array) to 4 (last element of the array)
i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 6
i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13
11, 12, 13, 5, 6
i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6
i = 4. 6 will move to the position after 5, and elements from 11 to 13 will move one position ahead of their current position.
5, 6, 11, 12, 13
Below is the Python implementation of the Insertion Sort Algorithm,
def insertionSort(list1 ):
for step in range(1, len(list1 )):
key = list1 [step]
j = list1 - 1
while j >= 0 and key < list1 [j]:
list1 [j + 1] = list1 [j]
j = j - 1
list1 [j + 1] = key
list1 = [25, 42, 10, 3, 6]
print(insertionSort(list1 ))
⭐ Merge Sort Algorithm
Merge Sort is a kind of Divide and Conquer algorithm in computer programming. But what
is divide and conquer?
This technique can be divided into the following three parts:
- Divide: This involves dividing the problem into some subproblem.
- Conquer: Sub problem by calling recursively until subproblem solved.
- Combine: The Sub problem Solved so that we will find a problem solution.
Merge sort first divides the array into equal halves and then combines them in a sorted manner.
Below is a simple example that illustrates how this algorithm works,
Below is the Python implementation of the Merge Sort Algorithm,
def mergeSort(myList):
if len(myList) > 1:
mid = len(myList) // 2
left = myList[:mid]
right = myList[mid:]
mergeSort(left)
mergeSort(right)
i = 0
j = 0
k = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
myList[k] = left[i]
i += 1
else:
myList[k] = right[j]
j += 1
k += 1
while i < len(left):
myList[k] = left[i]
i += 1
k += 1
while j < len(right):
myList[k]=right[j]
j += 1
k += 1
myList = [25, 42, 10, 3, 6]
print(mergeSort(myList))
⭐ Quick Sort Algorithm
Quick Sort is one of the really efficient Sorting algorithms. Quicksort is an algorithm based on the divide and conquer approach in which the array is split into subarrays and these sub-arrays are recursively called to sort the elements. Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot.
Below is how this algorithm works,
Step 1 − Choose the highest index value has a pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − Left points to the low index
Step 4 − Right points to the high
Step 5 − While value at left is less than pivot move right
Step 6 − While value at the right is greater than pivot move left
Step 7 − If both step 5 and step 6 does not match swap left and right
Step 8 − If left ≥ right, the point where they met is the new pivot
Below is the Python implementation of the Quick Sort Algorithm,
def partition(list1, low, high):
pivot = list1[high]
i = low - 1
for j in range(low, high):
if array[j] <= pivot:
i = i + 1
(list1[i], list1[j]) = (list1[j], list1[i])
(list1[i + 1], list1[high]) = (list1[high], list1[i + 1])
return i + 1
def quickSort(list1, low, high):
if low < high:
pi = partition(list1, low, high)
quickSort(list1, low, pi - 1)
quickSort(list1, pi + 1, high)
list1 = [25, 42, 10, 3, 6]
size = len(list1)
print(quickSort(list1, 0, size - 1))
Let me know below in the comment section which one is the best!
Related Post
If you spend 3–4 hours daily for 7 days, you will become a Junior Python Developer. I am providing this guideline using this android app called: Programming Hero.
I am taking all the examples from the Python learning app called Programming Hero: Coding Just Got Fun