Sắp xếp nổi bọt
Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Sắp xếp nổi bọt




Thông tin chung

Phân loại:
Giải thuật sắp xếp

Cấu trúc dữ liệu:
Ngẫu nhiên

Phức tạp thời gian:
Trung bình O(n2)

Phức tạp dữ liệu:
Không tốn thêm vùng nhớ

Tối ưu:
Không



 Sắp xếp nổi bọt (bubble sort) là một thuật toán sắp xếp đơn giản, với thao tác cơ bản là so sánh hai phần tử kề nhau, nếu chúng chưa đứng đúng thứ tự thì đổi chỗ (swap). Có thể tiến hành từ trên xuống (bên trái sang) hoặc từ dưới lên (bên phải sang). Sắp xếp nổi bọt còn có tên là sắp xếp bằng so sánh trực tiếp. Nó sử dụng phép so sánh các phần tử nên là một giải thuật sắp xếp kiểu so sánh.
Mục lục
[ẩn]
1 Giải thuật
1.1 Sắp xếp từ trên xuống
1.2 Sắp xếp từ dưới lên
2 Mã giả
2.1 Sắp xếp từ trên xuống
2.2 Sắp xếp từ dưới lên
2.3 Giàm bớt vòng duyệt
3 Thời gian tính
4 Mã thật ví dụ
4.1 Viết bằng Java
5 Xem thêm


[sửa] Giải thuật
[sửa] Sắp xếp từ trên xuống
Ví dụ:




Quá trình sắp xếp nổi bọt của 5 phần tử
Giả sử dãy cần sắp xếp có n phần tử. Khi tiến hành từ trên xuống, ta so sánh hai phần tử đầu, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ chúng cho nhau. Tiếp tục làm như vậy với cặp phần tử thứ hai và thứ ba và tiếp tục cho đến cuối tập hợp dữ liệu, nghĩa là so sánh (và đổi chố nếu cần) phần tử thứ n-1 với phần tử thứ n. Sau bước này phần tử cuối cùng chính là phần tử lớn nhất của dãy. Sau đó, quay lại so sánh (và đổi chố nếu cần) hai phần tử đầu cho đến khi gặp phần tử thứ n-2....
Ghi chú: Nếu trong một lần duyệt, không phải đổi chỗ bất cứ cặp phần tử nào thì danh sách đã được sắp xếp xong.
[sửa] Sắp xếp từ dưới lên
Săp xếp từ dưới lên so sánh (và đổi chỗ nếu cần) bắt đầu từ việc so sánh cặp phần tử thứ n-1 và n. Tiếp theo là so sánh cặp phần tử thứ n-2 và n-1,... cho đến khi so sánh và đổi chỗ cặp phần tử thứ nhất và thứ hai. Sau bước này phần tử nhỏ nhất đã được nổi lên vi trí trên cùng (nó giống như hình ảnh của các "bọt" khí nhẹ hơn được nổi lên trên). Tiếp theo tiến hành với các phần tử từ thứ 2 đến thứ n.
[sửa] Mã giả
[sửa] Sắp xếp từ trên xuống
procedure bubble_sort1(list L, number n) //n=listsize
For number i from n downto 2
for number j from 1 to (n - 1)
if L[j] > L[j + 1] //nếu chúng không đúng thứ tự
swap(L[j], L[j + 1]) //đổi chỗ chúng cho nhau
endif
endfor
endfor
endprocedure
[sửa] Sắp xếp từ dưới lên
procedure bubble_sort2(list L, number n) //n=listsize
For` number i from 1 ` n-1
for number j from n-1 downto i
if L[j] > L[j + 1] //nếu chúng không đúng thứ tự
swap(L[j], L[j + 1]) //đổi chỗ chúng cho nhau
endif
endfor
endfor
endprocedure
[sửa] Giàm bớt vòng duyệt
Nếu trong một lần duyệt nào đó với một i cố định khi vòng lặp j kết thúc mà không cần phải dổi chỗ cặp phần tử nào, nghiã là mọi cặp phân tử kề nhau đã đúng đúng thứ tự thì dãy đã được sắp xếp và không cần tiến hành vòng lặp tiếp theo. Do đó có thể dùng một cờ để kiểm soát việc này. Ta có một đoạn mã giả của thuật toán nổi bọt như sau:
procedure bubble_sort3(list L, number n)
i:= n
while i > 1 do
has_swapped := 0 //khởi tạo lại giá trị cờ
for number j from 1 to (i - 1)
if L[j] > L[j + 1] //nếu chúng không đúng thứ tự
swap(L[j], L[j + 1]) //đổi chỗ chúng cho nhau
has_swapped := 1 //có đổi chỗ ít