CISC 121 Lecture Notes - Lecture 37: Sorting Algorithm, Quicksort, Merge Sort

• School: Queen's University
• Department: Computing
• Course: CISC 121
• Professor: Wendy L Powley

Document Summary

The partition function you"ve seen above can be improved with a better choice of pivot value than the first value in the list/sub-list. This code selects the median of the first, last, and middle values as the pivot value. Merge sort is usually expressed as a not-in-place, o(n log n) (bset, average, and worst case), divide-and- conquer, recursive sortiung algorithm that is easy to code and to understand. Quicksort is usually expressed as an in-place, recursive sorting algorithm that typically performs in o(n log n) time, but that can degrade to o(n2) in the worst cases. A linked list is a sequence of data items (elements) in memory. Each element of a linked ist is created indepent of the others. Most programming languages have excellent built-in support for lists or list-like structures (e. g. arrays), but not for linked lists. A linked list is an alternative structure to a list (or array).