INTRO TO COMPUTER SCIENCE II
SORTING
CS162
Sorting
▪Putting a collection of data into ascending or descending order ▪ Uses comparison operator
▪ 5 8 1 12 7 -> 1 5 7 8 12
▪ Can be used to optimize code
▪ Searching for things is easier if data is organized
▪There are many different methods to sort data
▪ Bubble, Selection, Insertion, Merge, Quick, Heap, Counting… ▪ Shell, Comb, Bucket, Radix, Cocktail, Cycle, Sleep, Tim…
How do we choose a method?
▪Runtime
▪ Best, average, and worst case
▪Space usage
▪ Can it be sorted in-place, internally or does it
require external memory ▪ Stability
▪ If two elements are equal, they appear in the same order in the output as they were in the input
▪ Needed because data is often sorted based on only part of the data
Bubble sort
▪Simplest algorithm
▪Repeatedly swaps adjacent elements if they
are in the wrong order
▪ Stable
▪Slower on average
▪In-place, no significant extra space needed ▪ https://visualgo.net/bn/sorting
Selection sort
▪Data has two sections ▪ Already sorted
▪ Remaining unsorted
▪ Repeatedly finds the minimum element from the unsorted portion of the data and puts it at the beginning
▪Not stable by default
▪Consistent runtime
▪In-place, no significant extra space needed
Insertion sort
▪Somewhat similar to selection
▪ Divides the data into sorted and unsorted
▪Elements in the sorted portion are only sorted with respect to each other (not the entire array)
▪ An unsorted element could still be inserted somewhere in the middle of the sorted portion
▪Think of how you organize a hand of playing cards
▪ Stable
▪Best used for smaller datasets
Merge sort
▪A divide and conquer algorithm ▪ Divide – Break the given problem into
subproblems of the same type
▪ Conquer – Solve the subproblems
▪ Combine – Appropriately combine the answers
▪Key concepts
▪1) When two arrays are already sorted, it is
easy to combine them into one sorted array ▪2) An array of length “1” is already sorted
▪ Stable
▪Often used for large datasets, and externally
Sorting
A note on STL Sorting
▪sort() – uses hybrid algorithm called introsort (combination of quick, heap, and insertion)
▪stable_sort() – preserves order of equal elements