What makes a sorting result correct?
A correct sort produces an ordered sequence containing exactly the input elements; it changes their arrangement, not the data.
Study 09 Sorting Algorithms with 12 free online flashcards. Review key terms, definitions, and concepts with this interactive flashcard deck.
What makes a sorting result correct?
A correct sort produces an ordered sequence containing exactly the input elements; it changes their arrangement, not the data.
What does stability mean in sorting?
Stability preserves the original relative order of records with equal keys.
How does selection sort arrange elements?
Selection sort repeatedly finds the smallest element in the unsorted region and swaps it into the next output position.
How does insertion sort build a sorted array?
Insertion sort builds a sorted prefix one element at a time, shifting larger elements right to insert the next element.
What operation drives bubble sort?
Bubble sort repeatedly compares adjacent elements and swaps them when they are out of order.
What is merge sort’s divide-and-conquer strategy?
Merge sort divides the input into halves, recursively sorts each half, and merges the sorted halves.
What is the central operation in quicksort?
Quicksort partitions around a pivot, recursively sorts the smaller and larger partitions, and combines them around the pivot.
Why can quicksort degrade to quadratic time?
Quicksort has average-case O(nlogn) time with suitable pivots, but poor repeatedly unbalanced partitions cause O(n2) worst-case time.
How does heap sort produce ascending order?
Heap sort builds a max-heap, repeatedly moves the maximum root to the end, and restores the heap property.
What is the worst-case lower bound for comparison-based sorting?
A comparison-based sort has a worst-case lower bound of Ω(nlogn) for arbitrary input. Counting sort and radix sort can avoid this bound by using assumptions about the keys.
What does in-place mean for a sorting algorithm?
An in-place algorithm uses only a small amount of extra memory while rearranging the input collection. The standard implementations of selection, insertion, bubble, and heap sort are in-place.
What does extra space measure in sorting?
Extra space is the memory required beyond the input collection. For example, an array implementation of merge sort usually requires O(n) extra space, while standard heap sort uses O(1).
A progressive guide to how computers encode numbers, text, images, and sound as binary data, including the trade-offs and limits of digital representation.
A focused set of flashcards covering Python variables, data types, expressions, control flow, functions, input, output, and common programming practices.
Learn how Boolean expressions, logical operators, and conditional structures let programs make reliable decisions, including how to handle boundaries, branch order, and testing.
A structured guide to the main data structures, their operations, efficiency trade-offs, representations, and practical selection criteria.
A 14-question quiz on trees, binary trees, traversals, recursive algorithms, and binary search trees. The questions progress from foundational concepts to applied reasoning about structure, complexity, and BST operations.
A structured guide to comparison-based sorting algorithms, their complexity, stability, memory use, and practical selection criteria.
A progression through how data is organized, searched, exposed through software interfaces, and managed through abstraction layers in modern computer systems.
A medium-difficulty quiz on integrating problem definition, representation, algorithms, complexity analysis, testing, correctness, ethical evaluation, and documentation in a computer science capstone.
A practical guide to integrating problem definition, data representation, modular programming, algorithms, complexity analysis, testing, correctness, and ethical evaluation into a responsible computer science capstone.
This quiz covers process management, context switching and scheduling, multitasking, traps and interrupts, and RISC-V privilege transitions.