sorting-algorithms-flashcards
What is Selection Sort’s time complexity (best and worst case)?
O(n²) for both best and worst case - always needs to scan entire array multiple times
How does Selection Sort work?
Find minimum element in unsorted portion, swap it with first unsorted position, repeat
What are Selection Sort’s main advantages?
Simple to implement, performs well on small arrays, minimal memory usage (in-place)
What are Selection Sort’s main disadvantages?
Slow for large datasets, doesn’t adapt to partially sorted arrays, always O(n²)
What is Bubble Sort’s time complexity (best and worst case)?
Best case O(n) when already sorted, worst case O(n²)
How does Bubble Sort work?
Repeatedly step through the list, compare adjacent elements and swap if needed, until no swaps needed
What are Bubble Sort’s main advantages?
Simple to implement, best case O(n) on nearly sorted data, detects when array is sorted
What are Bubble Sort’s main disadvantages?
Very inefficient for large unsorted arrays, many swap operations, poor cache performance
What is Insertion Sort’s time complexity (best and worst case)?
Best case O(n) when nearly sorted, worst case O(n²)
How does Insertion Sort work?
Build sorted array one item at a time, insert each element into its correct position in sorted portion
What are Insertion Sort’s main advantages?
Efficient for small data, great for nearly sorted data, adaptive algorithm, in-place sorting
What are Insertion Sort’s main disadvantages?
Inefficient for large unsorted datasets, requires shifting elements during insertion
What is Merge Sort’s time complexity (best and worst case)?
O(n log n) for both best and worst case - consistently efficient
How does Merge Sort work?
Divide array into halves, sort recursively, merge sorted halves back together
What are Merge Sort’s main advantages?
Stable sort, guaranteed O(n log n), great for linked lists, predictable performance
What are Merge Sort’s main disadvantages?
Requires O(n) extra space, overkill for small arrays, not in-place
What is Quick Sort’s time complexity (best and worst case)?
Best/Average case O(n log n), worst case O(n²) but rare with good pivot
How does Quick Sort work?
Choose pivot, partition elements around pivot (smaller left, larger right), recursively sort partitions
What are Quick Sort’s main advantages?
Usually fastest in practice, in-place sorting, good cache performance, widely used
What are Quick Sort’s main disadvantages?
Unstable sort, worst case O(n²), recursive stack space needed, performance depends on pivot
What is Heap Sort’s time complexity (best and worst case)?
O(n log n) for both best and worst case - consistently efficient
How does Heap Sort work?
Build max heap from array, repeatedly extract max element and maintain heap property
What are Heap Sort’s main advantages?
In-place sorting, guaranteed O(n log n), constant extra space, good for priority queues
What are Heap Sort’s main disadvantages?
Unstable sort, slower in practice than quicksort, poor cache performance, complex implementation
Which sorting algorithms are stable?
Merge Sort, Bubble Sort, and Insertion Sort maintain relative order of equal elements
Which sorting algorithms are in-place?
Selection Sort, Bubble Sort, Insertion Sort, Quick Sort, and Heap Sort use O(1) extra space
For small arrays (<50 elements) which sorts are best?
Insertion Sort or Selection Sort due to low overhead and good cache performance
For nearly sorted data which algorithm is best?
Insertion Sort - achieves O(n) time complexity on nearly sorted arrays