4. Sorting

You can only sort comparable items

• int, double, char, strings, objects (in some cases)

Usually assumed: ascending order

Types of sorting

• internal sort - data to be sorted is all stored in computer’s main memory

• external sort - some data might be stored in an external, slower device

• in-place sort - rearranged the data in the same place, no copy is made

• Selection Sort

  • Brute Force Sort (exactly what it sounds like: swapping elements with nestled for loops)

  • Performs well but only for small lists

  • in-place

  • run time depends on the level of sorting in the original list

• Insertion Sort

  • inserts new element from unsorted list into sorted sublist

  • finds first element that’s larger and inserts new element before that one

  • Bad with huge lists, sensitive to initial ordering

• Bubble Sort

  • starts from the end, comparing versus the value at its current index

  • very popular

  • in-place

  • bad performance for big lists

• Quicksort

  • Uses median x