Module 5:
Basic Sorting Algorithms
The most popular sorting algorithms are:
• Bubble Sort
• Selection Sort
• Insertion Sort
• Quick Sort
• Merge Sort
Reference table for time complexities of
popular sorting algorithms:
Algorithm Best case Average case Worst case
Bubble Sort O(n) O(n2) O(n2)
Selection Sort O(n2) O(n2) O(n2)
Insertion Sort O(n) O(n2) O(n2)
Merge Sort O(n log(n)) O(n log(n)) O(n log(n))
Quick Sort O(n log(n)) O(n log(n)) O(n2)
Bubble Sort:
• Bubble Sort is one of the simplest sorting algorithms. It
works by repeatedly iterating through the list, comparing
adjacent elements, and swapping if they are in the wrong
order.
• Because of its poor performance, it is not practically used
and is just used for educational purposes.
Selection Sort:
• Selection Sort is one of the simplest sorting algorithms. It
works by creating a sorted array by finding and adding the
correct element in each iteration.
• The sequence (array) is divided into two parts: sorted part
and unsorted part. In each iteration, pick the smallest
element from the unsorted part, exchange it with the
leftmost unsorted element and move the boundary by one
place to include another element in the sorted part. After all
the iterations, the entire array gets sorted.
Insertion Sort:
• Insertion Sort is one of the simplest sorting algorithms. Most people
use this algorithm subconsciously while arranging playing cards in
their hands.
• The sequence (array) is divided into two parts: sorted part and
unsorted part. In each iteration, one element from the unsorted part
is moved to the correct position in the sorted part. After all the
iterations, the entire array gets sorted.
• Insertion Sort is one of the fastest sorting algorithms for sorting very
small input.
• See yourself:
• Advantages, Disadvantages
• Difference between bubble and selection sort
