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.
27 cards · basic cards · AI-written, checked twice. Edit anything.
- What is a sorting algorithm?
- 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?
- O(n^2)
- How does bubble sort work?
- Repeatedly swapping adjacent elements that are out of order, until the list is sorted
- What is the time complexity of selection sort?
- O(n^2)
- How does selection sort work?
- 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?
- O(n^2)
- How does insertion sort work?
- Building a sorted portion one element at a time, inserting each new element into its correct place
- When is insertion sort particularly efficient?
- On small or nearly-sorted datasets
- What is merge sort?
- A divide-and-conquer sorting algorithm that splits the list, sorts each half, and merges them
- What is the time complexity of merge sort?
- O(n log n) in all cases
- What is the space complexity of merge sort?
- O(n), due to the auxiliary arrays used during merging
- What is quicksort?
- A divide-and-conquer sorting algorithm that partitions elements around a pivot
- What is the average-case time complexity of quicksort?
- O(n log n)
- What is the worst-case time complexity of quicksort?
- O(n^2), typically when the pivot choice is poor
- What is a pivot in quicksort?
- An element chosen to partition the array into smaller and larger elements
FlashKeepers