CS2004_Sorting_Algorithms_Flashcards
(10 cards)
What is Bubble Sort?
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
✅ Example: Sorting [4, 2, 1] → swap 4 and 2, then 4 and 1 → repeat until sorted.
What is Insertion Sort?
Insertion Sort builds the sorted list one item at a time by repeatedly inserting new elements into the correct position.
✅ Example: Works well on small or nearly sorted arrays.
What is Selection Sort?
Selection Sort repeatedly finds the minimum element from the unsorted part and places it at the beginning of the sorted part.
✅ Example: Always O(n²), even if the list is partially sorted.
What is Merge Sort?
Merge Sort is a divide-and-conquer algorithm that splits the list in half, recursively sorts both halves, and then merges them together.
✅ Example: Always O(n log n), good for large lists.
What is Quick Sort?
Quick Sort is a divide-and-conquer algorithm that selects a pivot, partitions the list into elements less than and greater than the pivot, and recursively sorts the sublists.
✅ Example: Average O(n log n), worst-case O(n²) with poor pivot.
What is Radix Sort?
Radix Sort is a non-comparison sort that sorts numbers by digit, starting with the least significant digit (LSD).
✅ Example: Efficient when data is bounded and digit-based.
What is the best-case complexity of Insertion Sort?
O(n) — occurs when the list is already sorted.
Which sorting algorithms are stable?
Stable sorts: Bubble Sort, Insertion Sort, Merge Sort.
✅ A stable sort preserves the relative order of equal elements.
Which sorting algorithm is not comparison-based?
Radix Sort — it sorts by processing digits rather than comparing values directly.
What is meant by a stable sort?
A sorting algorithm is stable if it preserves the order of equal elements in the original list.
✅ Example: If two items have the same value, their order remains the same.
