Sắp xếp theo kiểu : Buble sort

Chia sẻ: Đặng Quang Hưng | Ngày: | Loại File: DOC | Số trang:2

0
177
lượt xem
29
download

Sắp xếp theo kiểu : Buble sort

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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, ...

Chủ đề:
Lưu

Nội dung Text: Sắp xếp theo kiểu : Buble sort

  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 . 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ằ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
  2. } 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.
Đồng bộ tài khoản