sorting-algorithms-flashcards

Question 1

What is Selection Sort’s time complexity (best and worst case)?

Answer 1

O(n²) for both best and worst case - always needs to scan entire array multiple times

Question 2

How does Selection Sort work?

Answer 2

Find minimum element in unsorted portion, swap it with first unsorted position, repeat

Question 3

What are Selection Sort’s main advantages?

Answer 3

Simple to implement, performs well on small arrays, minimal memory usage (in-place)

Question 4

What are Selection Sort’s main disadvantages?

Answer 4

Slow for large datasets, doesn’t adapt to partially sorted arrays, always O(n²)

Question 5

What is Bubble Sort’s time complexity (best and worst case)?

Answer 5

Best case O(n) when already sorted, worst case O(n²)

Question 6

How does Bubble Sort work?

Answer 6

Repeatedly step through the list, compare adjacent elements and swap if needed, until no swaps needed

Question 7

What are Bubble Sort’s main advantages?

Answer 7

Simple to implement, best case O(n) on nearly sorted data, detects when array is sorted

Question 8

What are Bubble Sort’s main disadvantages?

Answer 8

Very inefficient for large unsorted arrays, many swap operations, poor cache performance

Question 9

What is Insertion Sort’s time complexity (best and worst case)?

Answer 9

Best case O(n) when nearly sorted, worst case O(n²)

Question 10

How does Insertion Sort work?

Answer 10

Build sorted array one item at a time, insert each element into its correct position in sorted portion

Question 11

What are Insertion Sort’s main advantages?

Answer 11

Efficient for small data, great for nearly sorted data, adaptive algorithm, in-place sorting

Question 12

What are Insertion Sort’s main disadvantages?

Answer 12

Inefficient for large unsorted datasets, requires shifting elements during insertion

Question 13

What is Merge Sort’s time complexity (best and worst case)?

Answer 13

O(n log n) for both best and worst case - consistently efficient

Question 14

How does Merge Sort work?

Answer 14

Divide array into halves, sort recursively, merge sorted halves back together

Question 15

What are Merge Sort’s main advantages?

Answer 15

Stable sort, guaranteed O(n log n), great for linked lists, predictable performance

Question 16

What are Merge Sort’s main disadvantages?

Answer 16

Requires O(n) extra space, overkill for small arrays, not in-place

Question 17

What is Quick Sort’s time complexity (best and worst case)?

Answer 17

Best/Average case O(n log n), worst case O(n²) but rare with good pivot

Question 18

How does Quick Sort work?

Answer 18

Choose pivot, partition elements around pivot (smaller left, larger right), recursively sort partitions

Question 19

What are Quick Sort’s main advantages?

Answer 19

Usually fastest in practice, in-place sorting, good cache performance, widely used

Question 20

What are Quick Sort’s main disadvantages?

Answer 20

Unstable sort, worst case O(n²), recursive stack space needed, performance depends on pivot

Question 21

What is Heap Sort’s time complexity (best and worst case)?

Answer 21

O(n log n) for both best and worst case - consistently efficient

Question 22

How does Heap Sort work?

Answer 22

Build max heap from array, repeatedly extract max element and maintain heap property

Question 23

What are Heap Sort’s main advantages?

Answer 23

In-place sorting, guaranteed O(n log n), constant extra space, good for priority queues

Question 24

What are Heap Sort’s main disadvantages?

Answer 24

Unstable sort, slower in practice than quicksort, poor cache performance, complex implementation

Question 25

Which sorting algorithms are stable?

Answer 25

Merge Sort, Bubble Sort, and Insertion Sort maintain relative order of equal elements

Question 26

Which sorting algorithms are in-place?

Answer 26

Selection Sort, Bubble Sort, Insertion Sort, Quick Sort, and Heap Sort use O(1) extra space

Question 27

For small arrays (<50 elements) which sorts are best?

Answer 27

Insertion Sort or Selection Sort due to low overhead and good cache performance

Question 28

For nearly sorted data which algorithm is best?

Answer 28

Insertion Sort - achieves O(n) time complexity on nearly sorted arrays