Beginner LevelData Structures & Algorithms
Explain Bubble Sort, Selection Sort, and Insertion Sort with their complexities.
ā Interview Prompt: Compare the three basic O(NĀ²) sorting algorithms: Bubble Sort, Selection Sort, and Insertion Sort ā best/average/worst cases and when each is preferred.
Bubble Sort
Repeatedly swaps adjacent elements if out of order. Optimised with early exit if no swaps occurred in a pass.
ā¢
Best: $O(N)$ (already sorted, with flag), Worst/Average: $O(N^2)$.
Selection Sort
Finds the minimum in the unsorted portion and swaps it to the correct position. Always $O(N^2)$ regardless of input.
ā¢
Pro: Minimises number of swaps ($O(N)$ swaps vs $O(N^2)$ for Bubble).
Insertion Sort
Builds a sorted sub-array from left to right, inserting each element into its correct position.
ā¢
Best: $O(N)$ (nearly sorted input), Worst/Average: $O(N^2)$.
ā¢
When to use: Excellent for small arrays ($N < 20$) or nearly sorted data ā used as the base case inside Timsort.
Code Implementation Example
typescript
// Insertion Sort ā O(NĀ²) worst, O(N) best
function insertionSort(arr: number[]): number[] {
for (let i = 1; i < arr.length; i++) {
const key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // shift right
j--;
}
arr[j + 1] = key;
}
return arr;
}
console.log(insertionSort([5, 2, 4, 6, 1, 3])); // [1,2,3,4,5,6]š”Insertion Sort ā optimal for small or nearly-sorted arrays.
šÆ Interview Key Takeaway
Insertion Sort is the best O(NĀ²) algorithm for nearly-sorted data. All three have O(1) space. Prefer Merge/Quick sort for large N.
#DSA#Sorting#Bubble Sort#Insertion Sort#Beginner
Back to all Data Structures & Algorithms Questionsā