text: # Sorting: From Theory to Practice Why do we study sorting?
  
  ```Sorting: From Theory to Practice
  
  Why do we study sorting?
  
  
  
  
  Because we have to
  Because sorting is beautiful
  Example of algorithm analysis in a simple, useful setting
  How many of the n sorting algorithms to study?
  
  Why do we study more than one algorithm?
  • Some are good, some are bad, some are very, very sad
  
  
  
  Which sorting algorithm is best?
  Which sort should you call from code you write?
  http://www.sorting-algorithms.com/
  CPS 100, Spring 2010
  14.1
  Sorting out sorts
  
  Simple, O(n2) sorts --- for sorting n elements
  
  
  
  
  Divide and conquer sorts: O(n log n) for n elements
  
  
  
  Selection sort --- n2 comparisons, n swaps, easy to code
  Insertion sort --- n2 comparisons, n2 moves, stable, fast
  Bubble sort --- n2 everything, slow*, slower, and ugly*
  Quick sort: fast in practice, O(n2) worst case
  Merge sort: good worst case, great for linked lists, uses
  extra storage for vectors/arrays
  Other sorts:
  
  
  
  Heap sort, basically priority queue sorting
  Radix sort: doesn’t compare keys, uses digits/characters
  Shell sort: quasi-insertion, fast in practice, non-recursive
  CPS 100, Spring 2010
  14.2
  Selection sort: summary
  
  Simple to code n2 sort: n2 comparisons, n swaps
  void selectSort(String[] a) {
  int len = a.length;
  for(int k=0; k &lt; len; k++){
  int mindex = getMinIndex(a,k,len);
  swap(a,k,mindex);
  }
  }
  n
  S k = 1 + 2 + … + n = n(n+1)/2 = O(n2)
  k=1
  
  # comparisons
  
  
  Swaps?
  Invariant:
  CPS 100, Spring 2010
  Sorted, won’t move ?????
  final position
  14.3
  Insertion Sort: summary
  
  Stable sort, O(n2), good on nearly sorted vectors
   Stable sorts maintain order of equal keys
   Good for sorting on two criteria: name, then age
  void insertSort(String[] a){
  int k, loc; String elt;
  for(k=1; k &lt; a.length; ++k) {
  elt = a[k];
  loc = k;
  // shift until spot for elt is found
  while (0 &lt; loc &amp;&amp; elt.compareTo(a[loc-1]) &lt; 0) {
  a[loc] = a[loc-1];
  // shift right
  loc=loc-1;
  }
  a[loc] = elt;
  }
  }
  Sorted relative to
  ?????
  each other
  CPS 100, Spring 2010
  14.4
  Bubble sort: summary of a dog
  
  
  
  Really, really slow (to run), really really fast (to code)
  Can code to recognize already sorted vector (see insertion)
  • Not worth it for bubble sort, much slower than insertion
  
  void bubbleSort(String[] a){
  for(int j=a.length-1; j &gt;= 0; j--) {
  for(int k=0; k &lt; j; k++) {
  if (a[k] &gt; a[k+1])
  swap(a,k,k+1);
  }
  }
  Sorted, in final
  ?????
  }
  position
  “bubble” elements down the vector/array
  CPS 100, Spring 2010
  14.5
  Summary of simple sorts
  
  Selection sort has n swaps, good for “heavy” data
  
  moving objects with lots of state, e.g., …
  • In C or C++ this is an issue
  • In Java everything is a pointer/reference, so swapping is
  fast since it's pointer assignment
  
  Insertion sort good on nearly sorted data, stable!
  
  
  
  Also foundation for Shell sort, very fast non-recursive
  More complicated to code, but relatively simple, and fast
  Bubble sort is a travesty? But it's fast to code if
  you know it!
  
  Can be parallelized, but on one machine don’t go near it
  (see quotes at end of slides)
  CPS 100, Spring 2010
  14.6
  Brian Fox
  GNU Bash Shell (developer)
   Buddycast (co-developer)
  “each person has a sweet spot — a
  place where they are incredibly
  productive and at their happiest
  while doing so — okorians spend
  their lives living there — the okori
  sweet spot is the realization of the
  concept, the delivery of the
  impossible, from the germ of the
  idea to the instantiation of it”
  
  http://www.theokorigroup.com/sweet_spot
  CPS 100, Spring 2010
  14.7
  Quicksort: fast in practice
  
  Invented in 1962 by C.A.R. Hoare, didn’t
  understand recursion
  
  
  Worst case is O(n2), but avoidable in nearly all cases
  In 1997 Introsort published (Musser, introspective sort)
  • Like quicksort in practice, but recognizes when it will be bad
  and changes to heapsort
  void quick(String[], int left, int right){
  if (left &lt; right) {
  int pivot = partition(a,left,right);
  quick(a,left,pivot-1);
  quick(a,pivot+1, right);
  }
  }
  
  Recurrence?
  &lt;= X
  X
  &gt; X
  pivot index
  CPS 100, Spring 2010
  14.8
  Partition code for quicksort
  
  what we want
  &lt;= pivot
  &gt; pivot
  right
  left
  pIndex
  what we have
  ??????????????
  right
  left
  invariant
  &lt;=
  int partition(String[] a,
  int left, int right)
  {
  string pivot = a[left];
  int k, pIndex = left;
  for(k=left+1, k &lt;= right; k++) {
  if (a[k].compareTo(pivot) &lt;= 0){
  pIndex++;
  swap(a,k,pIndex);
  }
  }
  swap(a,left,pIndex);
  }
  
  &gt;
  ???
  right
  left
  pIndex
  CPS 100, Spring 2010
  k
  Easy to develop partition
  
  loop invariant:
   statement true each time loop
  test is evaluated, used to verify
  correctness of loop
  Can swap into a[left] before loop
   Nearly sorted data still ok
  14.9
  Analysis of Quicksort
  
  Average case and worst case analysis
  
  
  
  Reason informally:
  
  
  
  
  Two calls vector size n/2
  Four calls vector size n/4
  … How many calls? Work done on each call?
  Partition: median of three, then sort
  
  
  Recurrence for worst case: T(n) = T(n-1) + T(1) + O(n)
  T(n) = 2T(n/2) + O(n)
  Avoid bad performance on nearly sorted data
  In practice: remove some (all?) recursion, avoid lots
  of “clones”
  CPS 100, Spring 2010
  14.10
  Tail recursion elimination
  
  If the last statement is a recursive call, recursion can
  be replaced with iteration
  
  
  Call cannot be part of an expression
  Some compilers do this automatically
  void foo(int n){
  if (0 &lt; n) {
  System.out.println(n);
  foo(n-1);
  }
  }
  
  
  void foo2(int n){
  while (0 &lt; n) {
  System.out.println(n);
  n = n-1;
  }
  }
  What if print and recursive call switched?
  
  return n*factorial(n-1);
  CPS 100, Spring 2010
  14.11
  Merge sort: worst case O(n log n)
  
  Divide and conquer --- recursive sort
  
  Divide list/vector into two halves
  • Sort each half
  • Merge sorted halves together
  What is complexity of merging two sorted lists?
   What is recurrence relation for merge sort as described?
  T(n) =
  T(n) = 2T(n/2) + O(n)
  
  
  
  
  Array requires auxiliary storage (or very fancy coding)
  CPS 100, Spring 2010
  14.12
  Merge sort: lists or arrays or …
  
  Mergesort for arrays
  void mergesort(String[] a, int left, int right){
  if (left &lt; right) {
  int mid = (right+left)/2;
  mergesort(a, left, mid);
  mergesort(a, mid+1, right);
  merge(a,left,mid,right);
  }
  }
  
  What’s different when linked lists used?
  
  
  Do differences affect complexity? Why?
  How does merge work?
  CPS 100, Spring 2010
  14.13
  Summary of O(n log n) sorts
  
  Quicksort straight-forward to code, very fast
  
  
  Worst case is very unlikely, but possible, therefore …
  But, if lots of elements are equal, performance will be bad
  • One million integers from range 0 to 10,000
  • How can we change partition to handle this?
  
  Merge sort is stable, it’s fast, good for linked lists,
  harder to code?
  
  
  
  Worst case performance is O(n log n), compare quicksort
  Extra storage for array/vector
  Heapsort, good worst case, not stable, coding?
  
  Basically heap-based priority queue in a vector
  CPS 100, Spring 2010
  14.14
  Sorting in practice
  
  Rarely will you need to roll your own sort, but
  when you do …
  
  
  What are key issues?
  If you use a library sort, you need to understand the
  interface
  
  In C++ we have STL
  • STL has sort, and stable_sort
  
  
  In C sort is complex to use because arrays are ugly
  In Java guarantees and worst-case are important
  • Why won’t quicksort be used?
  
  Comparators allow sorting criteria to change
  CPS 100, Spring 2010
  14.15
  Non-comparison-based sorts
  
  
  
  
  lower bound: W(n log n) for
  comparison based sorts (like
  searching lower bound)
  bucket sort/radix sort are notcomparison based, faster
  asymptotically and in practice
  sort a vector of ints, all ints in
  the range 1..100, how?
   (use extra storage)
  numbers being sorted
   One-pass per digit
   Sort based on digit
  CPS 100, Spring 2010
  23 34 56 25 44 73 42 26 10 16
  16
  73 44
  26
  34
  42 23
  25 56
  10
  0
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10 42 23 73 34 44 25 56 26 16
  26
  44
  16 25
  10 23 34 42 56
  0
  1
  2
  3
  4
  5
  73
  6
  7
  8
  9
  10 16 23 25 26 34 42 44 56 73
  14.16
  Bubble Sort, A Personal Odyssey
  CPS 100, Spring 2010
  14.17
  11/08/77
  CPS 100, Spring 2010
  14.18
  17 Nov 75
  Not needed
  Can be tightened
  considerably
  CPS 100, Spring 2010
  14.19
  Jim Gray (Turing 1998)
  
  Bubble sort is a good
  argument for analyzing
  algorithm performance. It
  is a perfectly correct
  algorithm. But it's
  performance is among the
  worst imaginable. So, it
  crisply shows the
  difference between correct
  algorithms and good
  algorithms.
  (italics ola’s)
  CPS 100, Spring 2010
  14.20
  Brian Reid (Hopper Award 1982)
  Feah. I love bubble
  sort, and I grow weary
  of people who have
  nothing better to do
  Universities are good
  places to keep such
  people, so that they
  don't scare the general
  public.
  (continued)
  CPS 100, Spring 2010
  14.21
  Brian Reid (Hopper 1982)
  I am quite capable of squaring N with or without a calculator,
  and I know how long my sorts will bubble. I can type every
  form of bubble sort into a text editor from memory. If I am
  writing some quick code and I need a sort quick, as opposed
  to a quick sort, I just type in the bubble sort as if it were a
  statement. I'm done with it before I could look up the data
  type of the third argument to the quicksort library.
  I have a dual-processor 1.2 GHz Powermac and it sneers at
  your N squared for most interesting values of N. And my
  source code is smaller than yours.
  Brian Reid
  who keeps all of his bubbles sorted anyhow.
  CPS 100, Spring 2010
  14.22
  Niklaus Wirth (Turing award 1984)
  your view that Bubble Sort has
  hardly any merits. I think that it
  is so often mentioned, because it
  illustrates quite well the
  principle of sorting by
  exchanging.
  I think BS is popular, because it fits well
  into a systematic development of sorting
  algorithms. But it plays no role in actual
  applications. Quite in contrast to C, also
  without merit (and its derivative Java),
  among programming codes.
  CPS 100, Spring 2010
  14.23
  Guy L. Steele, Jr. (Hopper ’88)
  (Thank you for your fascinating paper
  and inquiry. Here are some off-the-cuff
  thoughts on the subject. )
  I think that one reason for
  the popularity of Bubble
  Sort is that it is easy to
  see why it works, and the
  idea is simple enough that
  one can carry it around in
  continued
  CPS 100, Spring 2010
  14.24
  Guy L. Steele, Jr.
  As for its status today, it may be an example of that
  phenomenon whereby the first widely popular version of
  something becomes frozen as a common term or
  cultural icon. Even in the 1990s, a comic-strip bathtub
  very likely sits off the floor on claw feet.
  … it is the first thing that leaps to mind, the thing that
  is easy to recognize, the thing that is easy to doodle on
  a napkin, when one thinks generically or popularly
  CPS 100, Spring 2010
  14.25
  Sorting Conundrums
  
  You have two arrays: names and expenditures (or
  batting average or GPA or …)
  
  
  
  
  Create POJO with name/cost that is-a Comparable
  
  
  String[] name, double[] costs
  Could pull from database via PHP, could read from file for
  bio prof, could …
  How do you sort by name or sort by cost?
  Reasons for doing this?
  Use selection/bubble and swap twice on indices
  
  Compare once, swap twice, why do it this way?
  CPS 100, Spring 2010
  14.26
  Sorting Conundrums (redux)
  
  You have a collection of MP3 files, roll your own
  iTunes
  
  
  
  You want to sort a million 32-bit integers
  
  
  Sort by artist, track, genre, …
  Would you move the large files around? Implications?
  You have a collection/database of a million strings
  (DNA, names, …) with lots of duplicates
  
  
  You call qsort in C, it’s really slow on some systems
  Alternatives? Reasons?
  CPS 100, Spring 2010
  14.27
  Owen O’Malley
  Debugging can be frustrating, but
  very rewarding when you find the
  cause of the problem. One of the
  nastiest bugs that I’ve found when I
  was at NASA and the Mars Explorer
  Rovers had just landed on Mars.
  http://sortbenchmark.org/
explanation: The provided text is a detailed lecture or presentation on sorting algorithms, covering various sorting techniques, their complexities, and practical considerations. It includes discussions on why sorting is studied, different types of sorting algorithms (e.g., selection sort, insertion sort, bubble sort, quicksort, mergesort, and radix sort), and their respective time complexities. The text also includes quotes from notable computer scientists and engineers about the merits and drawbacks of certain sorting algorithms, particularly bubble sort.
  
  The document does not contain a specific math question or a question and answer. It is primarily an educational resource on sorting algorithms.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: # Sorting: From Theory to Practice Why do we study sorting?
  
  ```Sorting: From Theory to Practice
  
  Why do we study sorting?
  
  
  
  
  Because we have to
  Because sorting is beautiful
  Example of algorithm analysis in a simple, useful setting
  How many of the n sorting algorithms to study?
  
  Why do we study more than one algorithm?
  • Some are good, some are bad, some are very, very sad
  
  
  
  Which sorting algorithm is best?
  Which sort should you call from code you write?
  http://www.sorting-algorithms.com/
  CPS 100, Spring 2010
  14.1
  Sorting out sorts
  
  Simple, O(n2) sorts --- for sorting n elements
  
  
  
  
  Divide and conquer sorts: O(n log n) for n elements
  
  
  
  Selection sort --- n2 comparisons, n swaps, easy to code
  Insertion sort --- n2 comparisons, n2 moves, stable, fast
  Bubble sort --- n2 everything, slow*, slower, and ugly*
  Quick sort: fast in practice, O(n2) worst case
  Merge sort: good worst case, great for linked lists, uses
  extra storage for vectors/arrays
  Other sorts:
  
  
  
  Heap sort, basically priority queue sorting
  Radix sort: doesn’t compare keys, uses digits/characters
  Shell sort: quasi-insertion, fast in practice, non-recursive
  CPS 100, Spring 2010
  14.2
  Selection sort: summary
  
  Simple to code n2 sort: n2 comparisons, n swaps
  void selectSort(String[] a) {
  int len = a.length;
  for(int k=0; k &lt; len; k++){
  int mindex = getMinIndex(a,k,len);
  swap(a,k,mindex);
  }
  }
  n
  S k = 1 + 2 + … + n = n(n+1)/2 = O(n2)
  k=1
  
  # comparisons
  
  
  Swaps?
  Invariant:
  CPS 100, Spring 2010
  Sorted, won’t move ?????
  final position
  14.3
  Insertion Sort: summary
  
  Stable sort, O(n2), good on nearly sorted vectors
   Stable sorts maintain order of equal keys
   Good for sorting on two criteria: name, then age
  void insertSort(String[] a){
  int k, loc; String elt;
  for(k=1; k &lt; a.length; ++k) {
  elt = a[k];
  loc = k;
  // shift until spot for elt is found
  while (0 &lt; loc &amp;&amp; elt.compareTo(a[loc-1]) &lt; 0) {
  a[loc] = a[loc-1];
  // shift right
  loc=loc-1;
  }
  a[loc] = elt;
  }
  }
  Sorted relative to
  ?????
  each other
  CPS 100, Spring 2010
  14.4
  Bubble sort: summary of a dog
  
  
  
  Really, really slow (to run), really really fast (to code)
  Can code to recognize already sorted vector (see insertion)
  • Not worth it for bubble sort, much slower than insertion
  
  void bubbleSort(String[] a){
  for(int j=a.length-1; j &gt;= 0; j--) {
  for(int k=0; k &lt; j; k++) {
  if (a[k] &gt; a[k+1])
  swap(a,k,k+1);
  }
  }
  Sorted, in final
  ?????
  }
  position
  “bubble” elements down the vector/array
  CPS 100, Spring 2010
  14.5
  Summary of simple sorts
  
  Selection sort has n swaps, good for “heavy” data
  
  moving objects with lots of state, e.g., …
  • In C or C++ this is an issue
  • In Java everything is a pointer/reference, so swapping is
  fast since it's pointer assignment
  
  Insertion sort good on nearly sorted data, stable!
  
  
  
  Also foundation for Shell sort, very fast non-recursive
  More complicated to code, but relatively simple, and fast
  Bubble sort is a travesty? But it's fast to code if
  you know it!
  
  Can be parallelized, but on one machine don’t go near it
  (see quotes at end of slides)
  CPS 100, Spring 2010
  14.6
  Brian Fox
  GNU Bash Shell (developer)
   Buddycast (co-developer)
  “each person has a sweet spot — a
  place where they are incredibly
  productive and at their happiest
  while doing so — okorians spend
  their lives living there — the okori
  sweet spot is the realization of the
  concept, the delivery of the
  impossible, from the germ of the
  idea to the instantiation of it”
  
  http://www.theokorigroup.com/sweet_spot
  CPS 100, Spring 2010
  14.7
  Quicksort: fast in practice
  
  Invented in 1962 by C.A.R. Hoare, didn’t
  understand recursion
  
  
  Worst case is O(n2), but avoidable in nearly all cases
  In 1997 Introsort published (Musser, introspective sort)
  • Like quicksort in practice, but recognizes when it will be bad
  and changes to heapsort
  void quick(String[], int left, int right){
  if (left &lt; right) {
  int pivot = partition(a,left,right);
  quick(a,left,pivot-1);
  quick(a,pivot+1, right);
  }
  }
  
  Recurrence?
  &lt;= X
  X
  &gt; X
  pivot index
  CPS 100, Spring 2010
  14.8
  Partition code for quicksort
  
  what we want
  &lt;= pivot
  &gt; pivot
  right
  left
  pIndex
  what we have
  ??????????????
  right
  left
  invariant
  &lt;=
  int partition(String[] a,
  int left, int right)
  {
  string pivot = a[left];
  int k, pIndex = left;
  for(k=left+1, k &lt;= right; k++) {
  if (a[k].compareTo(pivot) &lt;= 0){
  pIndex++;
  swap(a,k,pIndex);
  }
  }
  swap(a,left,pIndex);
  }
  
  &gt;
  ???
  right
  left
  pIndex
  CPS 100, Spring 2010
  k
  Easy to develop partition
  
  loop invariant:
   statement true each time loop
  test is evaluated, used to verify
  correctness of loop
  Can swap into a[left] before loop
   Nearly sorted data still ok
  14.9
  Analysis of Quicksort
  
  Average case and worst case analysis
  
  
  
  Reason informally:
  
  
  
  
  Two calls vector size n/2
  Four calls vector size n/4
  … How many calls? Work done on each call?
  Partition: median of three, then sort
  
  
  Recurrence for worst case: T(n) = T(n-1) + T(1) + O(n)
  T(n) = 2T(n/2) + O(n)
  Avoid bad performance on nearly sorted data
  In practice: remove some (all?) recursion, avoid lots
  of “clones”
  CPS 100, Spring 2010
  14.10
  Tail recursion elimination
  
  If the last statement is a recursive call, recursion can
  be replaced with iteration
  
  
  Call cannot be part of an expression
  Some compilers do this automatically
  void foo(int n){
  if (0 &lt; n) {
  System.out.println(n);
  foo(n-1);
  }
  }
  
  
  void foo2(int n){
  while (0 &lt; n) {
  System.out.println(n);
  n = n-1;
  }
  }
  What if print and recursive call switched?
  
  return n*factorial(n-1);
  CPS 100, Spring 2010
  14.11
  Merge sort: worst case O(n log n)
  
  Divide and conquer --- recursive sort
  
  Divide list/vector into two halves
  • Sort each half
  • Merge sorted halves together
  What is complexity of merging two sorted lists?
   What is recurrence relation for merge sort as described?
  T(n) =
  T(n) = 2T(n/2) + O(n)
  
  
  
  
  Array requires auxiliary storage (or very fancy coding)
  CPS 100, Spring 2010
  14.12
  Merge sort: lists or arrays or …
  
  Mergesort for arrays
  void mergesort(String[] a, int left, int right){
  if (left &lt; right) {
  int mid = (right+left)/2;
  mergesort(a, left, mid);
  mergesort(a, mid+1, right);
  merge(a,left,mid,right);
  }
  }
  
  What’s different when linked lists used?
  
  
  Do differences affect complexity? Why?
  How does merge work?
  CPS 100, Spring 2010
  14.13
  Summary of O(n log n) sorts
  
  Quicksort straight-forward to code, very fast
  
  
  Worst case is very unlikely, but possible, therefore …
  But, if lots of elements are equal, performance will be bad
  • One million integers from range 0 to 10,000
  • How can we change partition to handle this?
  
  Merge sort is stable, it’s fast, good for linked lists,
  harder to code?
  
  
  
  Worst case performance is O(n log n), compare quicksort
  Extra storage for array/vector
  Heapsort, good worst case, not stable, coding?
  
  Basically heap-based priority queue in a vector
  CPS 100, Spring 2010
  14.14
  Sorting in practice
  
  Rarely will you need to roll your own sort, but
  when you do …
  
  
  What are key issues?
  If you use a library sort, you need to understand the
  interface
  
  In C++ we have STL
  • STL has sort, and stable_sort
  
  
  In C sort is complex to use because arrays are ugly
  In Java guarantees and worst-case are important
  • Why won’t quicksort be used?
  
  Comparators allow sorting criteria to change
  CPS 100, Spring 2010
  14.15
  Non-comparison-based sorts
  
  
  
  
  lower bound: W(n log n) for
  comparison based sorts (like
  searching lower bound)
  bucket sort/radix sort are notcomparison based, faster
  asymptotically and in practice
  sort a vector of ints, all ints in
  the range 1..100, how?
   (use extra storage)
  numbers being sorted
   One-pass per digit
   Sort based on digit
  CPS 100, Spring 2010
  23 34 56 25 44 73 42 26 10 16
  16
  73 44
  26
  34
  42 23
  25 56
  10
  0
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10 42 23 73 34 44 25 56 26 16
  26
  44
  16 25
  10 23 34 42 56
  0
  1
  2
  3
  4
  5
  73
  6
  7
  8
  9
  10 16 23 25 26 34 42 44 56 73
  14.16
  Bubble Sort, A Personal Odyssey
  CPS 100, Spring 2010
  14.17
  11/08/77
  CPS 100, Spring 2010
  14.18
  17 Nov 75
  Not needed
  Can be tightened
  considerably
  CPS 100, Spring 2010
  14.19
  Jim Gray (Turing 1998)
  
  Bubble sort is a good
  argument for analyzing
  algorithm performance. It
  is a perfectly correct
  algorithm. But it's
  performance is among the
  worst imaginable. So, it
  crisply shows the
  difference between correct
  algorithms and good
  algorithms.
  (italics ola’s)
  CPS 100, Spring 2010
  14.20
  Brian Reid (Hopper Award 1982)
  Feah. I love bubble
  sort, and I grow weary
  of people who have
  nothing better to do
  Universities are good
  places to keep such
  people, so that they
  don't scare the general
  public.
  (continued)
  CPS 100, Spring 2010
  14.21
  Brian Reid (Hopper 1982)
  I am quite capable of squaring N with or without a calculator,
  and I know how long my sorts will bubble. I can type every
  form of bubble sort into a text editor from memory. If I am
  writing some quick code and I need a sort quick, as opposed
  to a quick sort, I just type in the bubble sort as if it were a
  statement. I'm done with it before I could look up the data
  type of the third argument to the quicksort library.
  I have a dual-processor 1.2 GHz Powermac and it sneers at
  your N squared for most interesting values of N. And my
  source code is smaller than yours.
  Brian Reid
  who keeps all of his bubbles sorted anyhow.
  CPS 100, Spring 2010
  14.22
  Niklaus Wirth (Turing award 1984)
  your view that Bubble Sort has
  hardly any merits. I think that it
  is so often mentioned, because it
  illustrates quite well the
  principle of sorting by
  exchanging.
  I think BS is popular, because it fits well
  into a systematic development of sorting
  algorithms. But it plays no role in actual
  applications. Quite in contrast to C, also
  without merit (and its derivative Java),
  among programming codes.
  CPS 100, Spring 2010
  14.23
  Guy L. Steele, Jr. (Hopper ’88)
  (Thank you for your fascinating paper
  and inquiry. Here are some off-the-cuff
  thoughts on the subject. )
  I think that one reason for
  the popularity of Bubble
  Sort is that it is easy to
  see why it works, and the
  idea is simple enough that
  one can carry it around in
  continued
  CPS 100, Spring 2010
  14.24
  Guy L. Steele, Jr.
  As for its status today, it may be an example of that
  phenomenon whereby the first widely popular version of
  something becomes frozen as a common term or
  cultural icon. Even in the 1990s, a comic-strip bathtub
  very likely sits off the floor on claw feet.
  … it is the first thing that leaps to mind, the thing that
  is easy to recognize, the thing that is easy to doodle on
  a napkin, when one thinks generically or popularly
  CPS 100, Spring 2010
  14.25
  Sorting Conundrums
  
  You have two arrays: names and expenditures (or
  batting average or GPA or …)
  
  
  
  
  Create POJO with name/cost that is-a Comparable
  
  
  String[] name, double[] costs
  Could pull from database via PHP, could read from file for
  bio prof, could …
  How do you sort by name or sort by cost?
  Reasons for doing this?
  Use selection/bubble and swap twice on indices
  
  Compare once, swap twice, why do it this way?
  CPS 100, Spring 2010
  14.26
  Sorting Conundrums (redux)
  
  You have a collection of MP3 files, roll your own
  iTunes
  
  
  
  You want to sort a million 32-bit integers
  
  
  Sort by artist, track, genre, …
  Would you move the large files around? Implications?
  You have a collection/database of a million strings
  (DNA, names, …) with lots of duplicates
  
  
  You call qsort in C, it’s really slow on some systems
  Alternatives? Reasons?
  CPS 100, Spring 2010
  14.27
  Owen O’Malley
  Debugging can be frustrating, but
  very rewarding when you find the
  cause of the problem. One of the
  nastiest bugs that I’ve found when I
  was at NASA and the Mars Explorer
  Rovers had just landed on Mars.
  http://sortbenchmark.org/
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The provided text is a detailed lecture or presentation on sorting algorithms, covering various sorting techniques, their complexities, and practical considerations. It includes discussions on why sorting is studied, different types of sorting algorithms (e.g., selection sort, insertion sort, bubble sort, quicksort, mergesort, and radix sort), and their respective time complexities. The text also includes quotes from notable computer scientists and engineers about the merits and drawbacks of certain sorting algorithms, particularly bubble sort.
  
  The document does not contain a specific math question or a question and answer. It is primarily an educational resource on sorting algorithms.
  
  Label: no-question