Sorting

                                           sorting
      6 3 9 2 7 1 5 ------------> 1 2 3 5 6 7 9
 

• Internal sort : records fit in internal memory (direcrt access)
• External sort : on external devices -- disk, tape (block transfer)

• T : >= NlogN (key comparisons)
• N²       : Selection, insertion, bubble -- elementary
• NlogN : quick(averages), heap(worst)
• N        : radix sort
 
• S : in place

• Stable     : 2 4 3 1 2 5 1 2 ---> 1 1 2 2 2 3 4 5
• Unstable : 2 4 3 1 2 5 1 2 ---> 1 1 2 2 2 3 4 5

• 3sort

if a > b than swap(a, b)        if a > c than swap(a, c)        if b > c than swap(b, c)

 Back to Sorting