🔀

Algorithms: Sorting, Searching & Graphs

96 cards · 🇺🇸 English

Sorting algorithms, binary search, and core graph traversal/search algorithms.

Study all 96 cards for free

Flashcards, quizzes, pixel-art games and a daily review that remembers for you.

Study this deck free

Try the first 10 cards

1 / 10

Question

Sorting algorithm

Knew itLearning

Tap the card for the answer · swipe right if you knew it, left if not

Already have an account? Sign in

Cards

1Sorting algorithm
An algorithm that puts elements of a list into an order (numerical or lexicographical, ascending or descending)
2What two conditions must the output of any sorting algorithm satisfy?
1) The output must be in monotonic order, and 2) The output must be a permutation of the input
3Time complexity of the best comparison-based sorting algorithms on average
O(n log n)
4Timsort
A widely used hybrid sorting algorithm combining merge sort, insertion sort, and additional logic, dating to 2002
5Stable sorting algorithm
A sorting algorithm that maintains the relative order of records with equal keys
6In-place sorting algorithm
A sorting algorithm that needs only O(1) memory beyond the items being sorted (sometimes O(log n) is considered in-place)
7comparison sorts vs non-comparison sorts
Comparison sorts examine data only by comparing two elements, while non-comparison sorts use other properties (like integer values)
8Adaptive sorting algorithm
An algorithm whose running time is affected by the presortedness of the input
9Best-case time complexity of bubble sort
O(n) when the list is already sorted
10Worst-case time complexity of quicksort
O(n²), which occurs when the pivot choices are consistently poor
11Memory complexity of merge sort
O(n) additional space for simple implementations
12Heapsort's time complexity
O(n log n) for best, average, and worst cases
13Is heapsort stable?
No, heapsort is not a stable sorting algorithm
14Key advantage of merge sort
It scales well to very large lists with guaranteed O(n log n) worst-case performance and is stable
15Space complexity of heapsort
O(1) - it's an in-place sorting algorithm
16What data structure does heapsort use?
A heap (a special type of binary tree)
17Partition operation in quicksort
Selecting a pivot element, moving all smaller elements before it and all greater elements after it
18Introsort
A hybrid sorting algorithm that combines quicksort, heapsort, and insertion sort, used in several STL implementations
19Average time complexity of insertion sort
O(n²)
20Key characteristic of selection sort
It makes exactly n swaps, making it useful when swapping is very expensive
21Shellsort
A variant of insertion sort that moves out-of-order elements more than one position at a time by sorting elements at varying gaps
22Worst-case time complexity problem with shellsort
It's an open problem and depends on the gap sequence used, ranging from O(n²) to O(n^(4/3))
23What programming languages use Timsort as their standard sort routine?
Python and Java (as of JDK7)
24Worst-case time complexity of bubble sort
O(n²)
25Comb sort
A sorting algorithm based on bubble sort that eliminates small values near the end of the list (turtles) by initially swapping elements at varying distances
26Counting sort
A non-comparison sorting algorithm that counts occurrences of each value, running in O(|S| + n) time where S is the set of possible values
27Radix sort
An algorithm that sorts numbers by processing individual digits, either from least significant digit (LSD) or most significant digit (MSD)
28Time complexity of radix sort
O(n · k) where n is the number of elements and k is the number of digits
29Bucket sort
A divide-and-conquer sorting algorithm that partitions an array into a finite number of buckets, then sorts each bucket individually
30Distribution sort
Any sorting algorithm where data is distributed from input to multiple intermediate structures which are then gathered and placed on output