sorting.md

Sorting

• daweedkob sorting_algos html visulisation

• Why My Teenage Code Was Terrible: Sorting Algorithms and Big O Notation

  • Big O
  • Sorting algorithums
  • Bubblesort, InertionSort, Quicksort
  • Worst case n^2
  • Bogosort (randomise it every time and check sorted)
  • Think about what works best for the problem you are trying to solve .. that might be a text file [software-engineering-skills]

• Sorting algorithms visualized using the Blender Python API

  • Pretty colors 9in animated gifs

• [algorithms]

• Sorting Algorithms Animations

  • The following animations illustrate how effectively data sets from different starting points can be sorted using different algorithms

• Comparison Sorting Algorithms

• xSortLab

• sorting.at

• visualgo.net/sorting

• Sorting Algorithm Visualization : Merge Sort

• Radix Sort Revisited - The ultimate sort?

• Sorting with REGEX back-refernces

• Youtube Merge-sort with Transylvanian-saxon (German) folk dance 4min

• Timsort — the fastest sorting algorithm you’ve never heard of

  • Timsort: A very fast , O(n log n), stable sorting algorithm built for the real world — not constructed in academia.
  • #python s shorting algorithm

Joke Sorting Algorithms

• Is this the simplest (and most surprising) sorting algorithm ever?
  • Algorithm 1 ICan’tBelieveItCanSort(A[1..n])

  •   for i = 1 to n do
      for j = 1 to n do
      if A[i] < A[j] then
      swap A[i] and A[j]
    

  • There is nothing good about this algorithm. It is slow – the algorithm obviously runs in Θ(n2) time, whether worst-case, average-case or best-case. It unnecessarily compares all pairs of positions, twice (but see Section 3). There seems to be no intuition behind it, and its correctness is not entirely obvious. You certainly do not want to use it as a first example to introduce students to sorting algorithms.

Time Sort

Each item - sleep for n seconds - n is value - when process wakes up, add to list This is crap - but runs in O(n) complexity - and is racy and inefficent - what does that tell us about O(n) measure?

Examples

• HackerNews: FreeBSD replaces bubblesort with mergesort on SYSINTs (twitter.com/cperciva)
  • https://cgit.freebsd.org/src/commit/?id=9a7add6d01f3c5f7eba811e794cf860d2bce131d