McGraw Hill Introduction To Algorithms (2nd Ed) >>

 HEAPSORT (112 - 127) 15 pages
  6    1    1,2,3,4,5,6,7
  6    2    1,2,3,4,5
  6    3    1,2,3
  6    4    1,2,3,4 >>

 SORTING IN LINEAR TIME (145 - 160) 15 pages
  8    1    1,2,3,4*
  8    3    1,2,3,4,5*
  8    4    1,2
  8    Pro  2,4,6 >>

COUNTING-SORT(A, B, k)
1 for i <-- 0 to k
2     do C[i] <-- 0
3 for j <-- 1 to length[A]
4     do C[A[j]]<-- C[A[j]] + 1
5   > C[i] now contains the number of elements equal to i.
6 for i <-- 1 to k
7     do C[i] <-- C[i] + C[i - 1]
8   > C[i] now contains the number of elements less than or equal to i.
9 for j <-- length[A] downto 1
10    do B[C[A[j]]] <-- A[j]
11       C[A[j]] <-- C[A[j]] - 1

Counting Sort is Stable... (The Equal Values are in given order in the Result)

RADIX-SORT(A, d)
1 for i <-- 1 to d
2 do use a stable sort to sort array A on digit i

BUCKET-SORT(A)
1 n <-- length[A]
2 for i <-- 1 to n
3     do insert A[i] into list B[|n A[i]|]
4 for i <-- 0 to n - 1
5     do sort list B[i] with insertion sort
6 concatenate the lists B[0], B[1], . . ., B[n - 1] together in order

 HASH TABLES (192 - 219) 27 pages
  11    1    1,2,3
  11    2    1,2,3,4*
  11    3    1,2,3,4
  11    4    1,2,3,4 >>

 BINARY SEARCH TREES (220 - 238) 18 pages
  12    1    1,2,3,4,5
  12    2    1,2,3,4,5,6,7,8,9
  12    3    1,2,3,4,6 >>

 RED-BLACK TREES (238 - 261) 23 pages
  13    1    1,2,6
  13    2    1,2,3
  13    3    1,2, 3, 6
  13    4    1, 2, 3, 4, 6, 7 >>

 B-TREES (371 - 388) 17 pages
  18    1    1, 2, 3, 4, 5
  18    2    1, 3, 5, 6 >>

 BINOMIAL HEAPS (388 - 405) 17 pages
  19    1    1, 2
  19    2    1, 2, 3, 5, 7 >>

 SORTING NETWORKS (614 - 632) 18 pages >>

 MATRIX OPERATIONS (632 - 673) 41 pages >>

 Show All