Sorting Algorithms: Bubble, Selection, Insertion, Merge, Quick
Understanding Sorting Algorithms
Algo Props: Well-defined inputs, clear & unambiguous, must be effective, must terminate.
Big O: Worst case (asymptotic tight upper). Big Omega: Best case (lower). Big Theta: Average.
N^2 Sorting Algorithms
n^2 Sorting: Bubble, Selection, Insertion (iterative)
Bubble Sort
Start with an unsorted array.
Loop through the array from the first element to the second-to-last element.
Compare each pair of adjacent elements.
If the current element is greater than the next element:
Swap them so the smaller element comes first.
End when no more swaps are made during a pass through the array, meaning the array is sorted.
Selection Sort
Start with an unsorted array.
Repeat the following steps until the array is sorted:
For each position in the array:
Find the smallest element in the unsorted part of the array.
Swap that smallest element with the first element of the unsorted part (to move it to the sorted part).
End when all elements are sorted.
Insertion Sort
Start with a sorted array & a value to insert.
Initialize:
Let arr[] be the array and n be the size of the array.
Step 1: Loop over each element in the array:
For i = 0 to n-1:
Set minIndex = i (initially assume the smallest element is at index i).
Step 2: Find the smallest element in the unsorted part:
For j = i+1 to n-1:
If arr[j] < arr[minIndex], set minIndex = j (update the index of the smallest element).
Step 3: Swap the found smallest element with the first unsorted element:
If minIndex is different from i, swap arr[i] with arr[minIndex].
End when all elements are in order.
Sort Specialities: Bubble – Biggest Last, Selection – Smallest first after each pass, Insertion – Fast when almost sorted
Divide and Conquer Sorting Algorithms
Merge Sort
Base Case: If the array has one element, it is already sorted.
If array.length <= 1, return the array (no further steps needed).
Step 1: Divide the array:
Find the middle index of the array: middle = array.length / 2.
Divide the array into two halves: left = array[0 ... middle-1] and right = array[middle ... array.length-1].
Step 2: Recursively apply merge sort to both halves:
Recursively sort the left half.
Recursively sort the right half.
Step 3: Merge the sorted halves:
Initialize an empty array result[] to store the merged elements.
Use two pointers, one for the left half and one for the right half.
Compare the first elements of both halves:
If the element from the left half is smaller, add it to result[] and move the pointer on the left.
If the element from the right half is smaller, add it to result[] and move the pointer on the right.
Repeat this until all elements from both halves are merged into result[].
Return the merged and sorted array.
Quick Sort (Pivot)
Base Case: If the array has one or zero elements, it is already sorted.
If array.length <= 1, return the array.
Step 1: Choose a pivot:
Select a pivot element (you can choose the first element, last element, or a random element, depending on your strategy).
Step 2: Partition the array:
Initialize two lists, left[] and right[].
For each element in the array (except the pivot):
If the element is less than the pivot, put it in the left[] list.
If the element is greater than or equal to the pivot, put it in the right[] list.
Step 3: Recursively sort the left and right lists:
Apply Quick Sort to the left[] list.
Apply Quick Sort to the right[] list.
Step 4: Combine the sorted left list, pivot, and sorted right list into one sorted array.
Return the final sorted array.
Specialities: QS – pivot always in right location, left smaller, right larger
Stability: Repeated elements are in same order as when sort began.
In-place: Sort using original array, minimal additional memory
