Sắp xếp theo kiểu : 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ẽ sosá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ệttừ cuối đến phần tử thứ 2, rồi từ cuối đến phần tử thứ 3, ...
Nội dung trích xuất từ tài liệu:
Sắp xếp theo kiểu : Buble sort 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ẽ sosá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ệttừ 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ặtnước .Code:void bublesort(double *a){ double temp; for (int i = 2; i = 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ằngcá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ốicù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 acó 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 } 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ủathuật toán này là khi M quá lớn thì khó thực hiện.