• Selection Sort

 

example:   S O R T I N G     G O R T I N S    G I R T O N S    G I N T O R S    G I N O T R S     G I N O R T S     G I N O R S T

for i := 1 to N-1 do {        min := i;        for j := i+1 to N do              if a[j] < a[min] then                 min := j;        swap(a[i], a[min]);   }

 
        T = N²/2 + NM (M = record size)

 Good for small N, large M

 

Back to Sorting

 
 

• Insertion Sort

              S O R T I N G
            O S R T I N G
            O R S T I N G
                        .
                        .
                        .
            I O R S T N G
      -limit I N O R S T G
            G I N O R S T
 

T = N²/4 + N²/8*M
 
• For almost sorted file
• Compare adjacent pairs only --> longer heap

 Back to Sorting