- .:: HVAOnline ::.

mình xin bổ xung thêm một vài thuật toán sắp xếp khác.

1. thuật toán sắp xếp nổi bọt (buble sort):
trong thuật toán này, các giá trị trong mảng sẽ được duyệt từ cuối lên đầu, tại mỗi bước sẽ so sánh giá trị của 2 phần tử kề nhau. nếu chúng bị ngược thứ tự thì đổi lại vị trí. sau 1 lần như vậy thì phần tử có giá trị nhỏ nhất sẽ được chuyển về đầu mảng. và quá trình tiếp tục duyệt từ cuối đến phần tử thứ 2, rồi từ cuối đến phần tử thứ 3, ...
sở dĩ gọi là nổi bọt vì quá trình so sánh giữa các cặp phần tử giống như "bọt" nổi trên mặt nước smilie

.

Code:

void bublesort(double *a){

   double temp;

   for (int i = 2; i <= n; i++)

     for (int j = n; j >= i; j--)

       if (a[j] < a[j-1]) {

         temp = a[j];

         a[j] = a[j+1];

         a[j+1] = temp;

       }

 }

thuật toán này có độ phức tạp là O(n^2).

2. thuật toán sắp xếp đếm phân phối (distribution counting):
thuật toán này được áp dụng trong trường hợp đặc biệt, khi mà tất cả các giá trị trong mảng đều là số nguyên và thuộc khoảng [0..M] đã biết.
ý tưởng của thuật toán là đếm xem trong khoảng [0..M] đó có bao nhiêu giá trị 0 (giả sử là a), bao nhiêu giá trị 1 (giả sử là b), ..., bao nhiêu giá trị M (giả sử là z). sau đó xếp lại mảng bằng cách đặt a phần tử 0 ở đầu, tiếp theo đặt b phần tử 1 tiếp theo, ..., và đặt z phần tử M ở cuối cùng.
để giảm thiểu thì việc đếm trên không đếm những giá trị không có trong mảng. giả sử mảng a có các giá trị a[1], a[2], ..., a[k] trong tổng số n phần tử thì chỉ đếm số lần lặp lại của k giá trị đó.

Code:

double *distributioncounting(double *a){

   int c[M+1]; /* lưu số lần xuất hiện của các phần tử mảng a */

   int v;

   double b[n];

   for (int i = 0; i <= M; i++) c[i] = 0;

   for (i = 1; i <= n; i++) c[a[i]]++; /* đếm số lần xuất hiện của a[i] trong khoảng [0..M] */

   for (i = 1; i <= M; i++) c[i] += c[i-1]; /*tính vị trí cuối của mỗi đoạn con */

   for (i = n; i > 0; i--) {

     v = a[i];

     b[c[v]] = a[i];

     c[v]--;

   }

   return b;

 }

độ phức tạp của thuật toán này là O(max(M, n)), do kết quả của phép đếm. nhược điểm của thuật toán này là khi M quá lớn thì khó thực hiện.