PP sắp xếp : heap sort - counting sort

COUTING SORT
1.Ý tưởng
Couting sort không sắp xếp bằng cách so sánh-hoán đổi vị trí các vị trí các phần tử, mà dựa trên thông tin của các phần tử để sắp xếp.Nói là vậy thôi chứ Couting sort cũng không khó hiểu lắm đâu! (
COUTING SORT sắp xếp bằng cách đếm số lượng mỗi phần tử, rồi sau đó dặt vào vị trí đáng ra nó phải ở “đó”.
Ví dụ : ta có mảng 9 8 4 5 7 9 5 4 1 4

Phần tử
0
1
2
3
4
5
6
7
8
9

Số Lượng
0
1
0
0
3
2
0
1
1
1




Theo lẽ bình thường, chỉ cần sắp ra thôi, tức là ta đặt:
- Có 0 số 0 nên không cần đưa ra
- Có 1 số 1 nên đặt nó ở vị trí đầu
- Tiếp tục, có 3 số 4 nên 3 số 4 sẽ đặt ở 3 vị trí tiếp theo
-Cứ như thế ta sẽ có dãy số 1 4 4 4 5 5 7 8 9
Tuy nhiên đây là cách thực hiện của con người, còn thực hiện trên máy hơi khác một tí.

2.Giải thuật
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 // C[ A[i] ] ++;
5 // C[i] bây giờ chứa số lượng của phần tử có “giá trị là i”
6 for i ← 1 to k
7 do C[i] ← C[i] + C[i - 1]
8 //C[i] bây giờ chứa số lượng của phần tử ”nhỏ hơn hoặc bằng i”.
9 for j ← length[A] downto 1
10 do B[C[A[j]]] ← A[j]
11 C[A[j]] ← C[A[j]] – 1

Để hiểu cho “chắc cú” , chúng ta cùng xem “minh họa trên giấy” sau :
- Dòng 1, 2
1
2
3
4
5

5
6
5
9
7


A
0
1
2
3
4
5
6
7
8
9

0
0
0
0
0
0
0
0
0
0


C

- Dòng 3, 4
1
2
3
4
5

5
6
5
9
7


A
0
1
2
3
4
5
6
7
8
9

0
0
0
0
0
2
1
1
0
1


C
- Dòng 6, 7
1
2
3
4
5

5
6
5
9
7


A
0
1
2
3
4
5
6
7
8
9

0
0
0
0
0
2
3
4
4
5


C

- Dòng 9, 10, 11
1
2
3
4
5

5
6
5
9
“7”


A(j = 5)

1
2
3
4
5




“7”


 B
0
1
2
3
4
5
6
7
8
9

0
0
0
0
0
2
3
“4”
4
5


C


1
2
3
4
5

5
6
5
“9”
7


A( j= 4)

1
2
3
4
5




7
“9”

 B
0
1
2
3
4
5
6
7
8
9

0
0
0
0
0
2
3
3
4
“5”


C


1
2
3
4
5

5
6
“5”
9
7


A( j = 3)

1
2
3
4
5


“5”

7
9

 B
0
1
2
3
4
5
6
7
8
9

0
0
0
0
0
“2”
3
3
4
4


C


1
2
3
4
5

5
“6”
5
9
7


A(j = 2)

1
2
3
4
5


5
“6”
7
9

 B
0
1
2
3
4
5
6
7
8
9

0
0
0
0
0
1
“3”
3
4
4


C




1
2
3
4
5

“5”
6
5
9
7


A(j = 1)

1
2
3
4
5

“5”
5
6
7
9

 B
0
1
2
3
4
5
6
7
8
9

0
0
0
0
0
“1”
2
3
4
4


C


1
2
3
4
5

5
6
5
9
7


A

1
2
3
4
5

5
5
6
7
9

 B
0
1
2
3
4
5
6
7
8
9

0
0
0
0
0
0
2
3
4
4


C