Data structures & algorithmsLesson 1 of 2 in the course Algorithm analysis and sorting

Sorting Algorithms: Correctness, Stability, Methods, and Trade-offs

5 flashcards · 5 quiz questions · 5 match pairs · 4 fill-in sentences · English

Save course
Lesson progress
0 / 5

Your progress is kept in this browser only.Sign up to save it

Summary

Sorting arranges the elements of a collection according to a chosen order. This lesson introduces the requirements for a correct sort and the main ways sorting algorithms are described.

A sorting algorithm rearranges elements into an order, commonly numerical or lexicographical (dictionary) order, either ascending or descending. Sorting supports efficient searching and merging, can make data easier to inspect, and can provide a canonical arrangement for consistent storage or comparison.

All flashcards

What does stability mean in sorting records?
Records with equal keys retain their original relative order.
What is an in-place sorting algorithm?
A sort that uses little additional memory beyond the data being sorted.
What is a comparison sort?
A sorting algorithm that determines order by comparing pairs of elements.
What does selection find?
The item at a specified rank, such as the kth-smallest item.
What is an index sort?
A method that sorts references or indices instead of moving full records.

Quiz questions

  1. To sort records by a secondary key and then a primary key using two passes, which approach preserves the secondary-key ordering?Answer: Sort by the secondary key first, then stably sort by the primary key.
  2. For comparison sorting of arbitrary inputs, what lower bound applies to the number of comparisons in the general case?Answer: On the order of nlog⁡nn\log n comparisons.
  3. What is a characteristic advantage of selection sort when writes or swaps are costly?Answer: It makes no more than about nn swaps.
  4. What can cause quicksort to take quadratic time?Answer: Repeated pivots produce highly unbalanced partitions.
  5. How does external sorting handle data that does not fit in main memory?Answer: Sort memory-sized chunks, then merge the sorted results.

Based on the Wikipedia article Sorting algorithm, licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.

More in Data structures & algorithms

All Data structures & algorithms lessons
Data structures & algorithmsBinary Heaps: Ordering, Array Operations, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Data structures & algorithmsBinary Search Trees: Ordering, Operations, Height, and Uses5 flashcards · 5 quiz questions · 4 gamesPlay free →Data structures & algorithmsMerge Sort: Algorithms, Complexity, Variants, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Data structures & algorithmsTrie Structure, Operations, Compression, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →