CPSC 319 Lecture Notes - Lecture 4: Quicksort, Array Data Structure, Selection Sort

• School: University of Calgary
• Department: Computer Science
• Course: CPSC 319
• Professor: Leonard Manzara

Document Summary

Internal sort: data is kept in primary memory i. e. in ram, using arrays. External sort: data is kept in secondary storage i. e. on disk or tape: usually requires special sorting techniques. In-place sort: a sort achieved by exchanging items in place within an array i. e. does not use extra memory: some sorts use extra memory for speed reasons. Stable sort: a sort that preserves the relative order of equal keys: e. g. Sort a list of people first by name, then by age. Ensures that people of the same age remain in alphabetic order. Is usually done by considering the number of: comparisons, data movements i. e. exchanges or swaps . The efficiency of a sort may depend on the initial ordering of data. We measure the number of comparisons and data movements for the: best case: data already in order, worst case: data in reverse order, average case: data in random order.