sorting.md

Sorting

Insertion Sorting

• Total time required to sort $$N$$ element sequence proportional to $$N$$ plus # of inversions → nearly sorted inputs can be sorted in nearly linear time

Shellsort

• Variation of insertion sort → use insertion sort repeatedly on evenly spaced subsequences of elements, decreasing spacing each time until ending up w/ ordinary insertion sort (diminishing increment sort)
• Starting by sorting widely spaced elements → can reduce # of inversions much more quickly than ordinary insertion sort (each subsequent insertion sorts go faster)
• Sorting w/ increment of $$k$$ = sort items $$0, k, 2k, \cdots$$ → $$1, k + 1, 2k + 1, \cdots$$ → $$2, k + 2, 2k + 2, \cdots$$, up to subsequence starting w/ item $$k - 1$$
• Any sequence that ends w/ increment of 1 will produce results
• Certain sequences better than others
  • Sequences $$2^{p} - 1, 2^{p - 1} - 1, \cdots, 1$$ where $$p = \lfloor \lg{N} \rfloor$$ results in overall running time of $$O(N^{\frac{3}{2}})$$

Quicksort

• Maximum partition size limits # of inversions in sequences → limits execution time of insertion sort
• # of inversions in sequences partitioned by quicksort equal to sum of # of inversions in individual partitions
• Once max partition size reduced to constant → total # of inversions linear in size of entire sequence
• Insertion sort has better constant factors than quicksort → common modification to quicksort = apply insertion sort once max partition size reduced below predetermined threshold
• Each partitioning operation requires linear time in size of subsequence being partitioned
• In worst case, maximum partition size reduced by one on each step → $$O(N^{2})$$ runtime
• Various strategies $$\exists$$ for choosing pivots, including taking small random samples of subsequence

Straight Selection Sorting

• Select successively smaller/larger items from list & add to output sequence
• Looks at all unprocessed data on each pass → performs no better for nearly sorted inputs than random or reverse-sorted inputs (unlike insertion sort)
• Possible optimization = remember order of other items on each pass through (turns into heapsort?)

Heapsort

• Complete binary tree: Each level of tree completely full, w/ possible exception of lowest level → nodes on lowest level located as far to left of level as possible

Merge Sorting

• Many variations, all of which follow divide-and-conquer scheme
  • Divide data into subsequences → recursively sort subsequences → merge sorted subsequences into increasingly large sorted sequences
• For merging large numbers of sequences → use variety of priority queue (or heap) to keep track of which sequence currently has smallest item
• B/c deals w/ data sequentially & requires only enough memory to buffer input & output (finite amount) → merge sorting ideally suited to external sorting (amount of data to be sorted exceeds capacity of primary memory by arbitrarily large amounts)
  • Size of sorted data limited only by size of secondary memory
  • Sort stream of data?
• B/c of divide & conquer character → merge sorting eminently parallelizable

Beyond Comparisons: Radix Sort & Counting Sort

• Comparison based sorts used binary comparisons $$(<, >, \leq, \geq)$$ to control algorithms
  • Theoretical lower bound on # of comparisons (& thus overall operations) needed to sort $$N$$ items → $$\Omega(N \lg{N})$$
• By exploiting more properties of data being sorted than ordering relation, can arrive at different bounds
• Radix sorting: Uses digits/bytes constituting data to make multi-way decisions → able to sort $$B$$ bytes of data in $$O(B)$$ time
  • Comparing $$O(B)$$ to $$O(N \log{N})$$ comparisons to sort $$N$$ (multi-byte) records tricky
    • If assume in worst case, comparisons take time proportional to # of bytes of data being compared → radix sorting should win
    • For practical purposes, must consider constant factors
• Idea behind radix sorting = view keys to be sorted sequences of numerals consisting of digits in finite radix ($$R$$)
  • ASCII character strings = base-256 numerals
  • Pad all keys to same # of digits (on left/right, depending on sorting order)
    • Right for strings, left for #s
  • If common length of keys is now $$D$$ digits, sort keys (up to) $$D$$ times (once on first digit, once on second, etc.)
  • Precise logistics differ depending on whether processing digits left to right (MSD radix sort) or right to left (LSD radix sort)
• MSD radix sort → each sort rearranges dat into sections that can be sorted independently, sections already ordered correctly w/ respect to each other
  • Further refine sections having more than one key by later character positions until all sections contain just one item
• LSD radix sort → sort all data together on each pass, carefully maintaining previously established order for keys w/ same digit in position currently being sorted
• Can accomplish each one-character sorts in $$O(N + R)$$ time using stable counting sort
  • First count # of keys containing each possible digit (0 to $$R - 1$$) at current character position ($$k$$) → easy to compute # of keys whose $$k^{\text{th}}$$ is $$d$$, & thus # of keys left of those whose $$k^{\text{th}}$$ is $$d$$ → allows another pass through keys, moving to proper positions