Data Structures, unit: Sorting Algorithms. Core concepts, terminology, and worked-example cues a college student meets for this unit, building on prior units without repeating them. Front: a term, concept, or short problem cue. Back: the definition, explanation, or answer.
37 cards · basic cards · AI-written, checked twice. Edit anything.
- What is a sorting algorithm?
Show answer
An algorithm that arranges elements of a list into a specific order- What is the time complexity of bubble sort in the average and worst case?
Show answer
O(n^2)- How does bubble sort work?
Show answer
Repeatedly swapping adjacent elements that are out of order, until the list is sorted- What is the time complexity of selection sort?
Show answer
O(n^2)- How does selection sort work?
Show answer
Repeatedly finding the minimum element from the unsorted portion and moving it to the front- What is the time complexity of insertion sort in the average and worst case?
Show answer
O(n^2)- How does insertion sort work?
Show answer
Building a sorted portion one element at a time, inserting each new element into its correct place- When is insertion sort particularly efficient?
Show answer
On small or nearly-sorted datasets- What is merge sort?
Show answer
A divide-and-conquer sorting algorithm that splits the list, sorts each half, and merges them- What is the time complexity of merge sort?
Show answer
O(n log n) in all cases- What is the space complexity of merge sort?
Show answer
O(n), due to the auxiliary arrays used during merging- What is quicksort?
Show answer
A divide-and-conquer sorting algorithm that partitions elements around a pivot- What is the average-case time complexity of quicksort?
Show answer
O(n log n)- What is the worst-case time complexity of quicksort?
Show answer
O(n^2), typically when the pivot choice is poor- What is a pivot in quicksort?
Show answer
An element chosen to partition the array into smaller and larger elements
FlashKeepers