Sắp xếp các nút của một cấu trúc theo thứ tự tăng dần (hay giảm dần) là một công việc được thực hiện thường xuyên. Với một cấu trúc đã được sắp xếp chúng ta rất thuận tiện khi thực hiện các tác vụ trên cấu trúc như tìm kiểm, trích lọc, duyệt cấu trúc ....
Có hai loại giải thuật sắp xếp được dùng phổ biến trong khoa học máy tính là sắp xếp nội (internal sorting) và sắp xếp ngoại (external sorting):
- Với loại sắp xếp nội thì toàn bộ dữ liệu cần sắp xếp được đưa vào bộ nhớ trong, do vậy kich thước dữ liệu cần sắp xếp không lớn, tuy nhiên thời gian sắp xếp được thực hiện rất nhanh.
- Với loại sắp xếp ngoại thì chỉ một phần nhỏ dữ liệu cần sắp xếp được đưa vào bộ nhớ trong, phần lớn dữ liệu còn lại được lưu ở bộ nhớ ngoài (như đĩa từ băng từ, ...), kích thước dữ liệu cần sắp xếp lúc này rất lớn (phụ thuộc vào kích thước của đĩa từ, băng từ, ...), và thời gian sắp xếp thực hiện rất chậm.
Sau đây ta chỉ nguyên cứu về giải thuật sắp xếp nội
Nội dung sẽ trình bầy:
->->
- Bubble sort. (Nổi bọt, nổi bong bóng)
- Quick sort. (Sắp xếp nhanh)
- Simple selection sort. (Sắp xếp chọn)
- Heap sort. (Sắp xếp vun đống)
- Simple insertion sort.(Sắp xếp chèn)
- Shell sort.
- Merge sort. (Sắp xếp hòa nhập)
Bubble sort
Phương pháp này sẽ duyệt danh sách nhiều lần, trong mỗi lần duyệt sẽ lần lượt so sánh cặp nút thứ i và thứ i+1 và đổi chỗ hai nút này nếu chúng không đúng thứ tự.
Ví dụ cho một dãy số đơn giản và sắp xếp cho nó tăng dần.
25 55 45 90 10
Và đây sẽ minh họa quá trình so sánh và đổi chỗ trong lần duyệt đầu tiên.
So sánh nút thứ i với nút thứ i+1 nếu nút thứ i > nút i+1 thì đổi chỗ 2 nút với nhau. Nếu không tiếp tục so sánh tiếp.
Danh sách sau khi biến đổi lần thứ nhất.
25 45 55 10 90.
Ta nhận thấy phần tử 90 lớn nhất được đưa về cuối danh sách, cứ tuần tự kiểm tra n lần như vậy ta sẽ được một danh sách tăng dần.
Tiếp giờ ta sẽ Mô Tả Giải Thuật Bubble Sort
Cài đặt giải thuật Bubble sort
Một cách biểu diễn khác của thuật toán:
- Swap là hàm đổi chỗ hai biến cho nhau, dùng để hoán đổi hai giá trị của hai vị trí trong mảng cần sắp xếp.
- Hàm BubbleSort là hàm nổi bọt, so sánh hai vị trí liên kề nhau, nếu không đúng tính chất (tăng dần, không tăng, giảm dần, không giảm) thì đổi chỗ
Nhận xét: Giải thuật bubble sort dễ hiểu nhưng không tối ưu vì thời gian thực hiện giải thuật dài.
Download hàm sắp xếp nổi bọt miễn phí
1. Bài toán
Cho dãy X = {X1, X1, ..., Xn}, hãy sắp xếp dãy theo chiều không giảm.
2. Ý tưởng
- Thao tác cơ bản của thuật toán này là so sánh hai phần từ kề nhau X[i] và X[i-1], nếu chúng đứng chưa đúng thứ tự thì đổi chổ cho nhau. Sau một chu trình so sánh, nếu thực hiện từ phải sang trái phần từ đầu tiên (hoặc cuối cùng nếu theo chiều ngược lại) đứng đúng vị trí, bỏ qua phần từ đó.
- Tiếp tục thực hiện với dãy là những phần tử còn lại.
3. Giải thuật
- Bước 1: i=1
- Bước 2: Lần lượt so sánh và đổi chổ (nếu cần) từ phải sang trái đối với các phần từ từ X[n] đến X[i]
- Bước 3: i=i+1
- Bước 4:
* Nếu i < n, quay lại Bước 2.
* Ngược lại, dừng, dãy đã cho đã sắp xếp đúng vị trí.
Mô tả phương pháp:Cho dãy X = {X1, X1, ..., Xn}, hãy sắp xếp dãy theo chiều không giảm.
2. Ý tưởng
- Thao tác cơ bản của thuật toán này là so sánh hai phần từ kề nhau X[i] và X[i-1], nếu chúng đứng chưa đúng thứ tự thì đổi chổ cho nhau. Sau một chu trình so sánh, nếu thực hiện từ phải sang trái phần từ đầu tiên (hoặc cuối cùng nếu theo chiều ngược lại) đứng đúng vị trí, bỏ qua phần từ đó.
- Tiếp tục thực hiện với dãy là những phần tử còn lại.
3. Giải thuật
- Bước 1: i=1
- Bước 2: Lần lượt so sánh và đổi chổ (nếu cần) từ phải sang trái đối với các phần từ từ X[n] đến X[i]
- Bước 3: i=i+1
- Bước 4:
* Nếu i < n, quay lại Bước 2.
* Ngược lại, dừng, dãy đã cho đã sắp xếp đúng vị trí.
Phương pháp này sẽ duyệt danh sách nhiều lần, trong mỗi lần duyệt sẽ lần lượt so sánh cặp nút thứ i và thứ i+1 và đổi chỗ hai nút này nếu chúng không đúng thứ tự.
Ví dụ cho một dãy số đơn giản và sắp xếp cho nó tăng dần.
25 55 45 90 10
Và đây sẽ minh họa quá trình so sánh và đổi chỗ trong lần duyệt đầu tiên.
So sánh nút thứ i với nút thứ i+1 nếu nút thứ i > nút i+1 thì đổi chỗ 2 nút với nhau. Nếu không tiếp tục so sánh tiếp.
- So sánh 25 với 55:kiểm tra 25 < 55 -> Sai không đổi chỗ.
- So sánh tiếp 55 với phần tử tiếp theo là 45: 55 > 45 -> Đúng đổi chỗ 45 với 55
- So sánh tiếp 55 với 90: 55 < 90 -> sau không đổi chỗ.
- So sánh tiếp 90 với 10: 90 > 10 -> đúng đổi chỗ 90 cho 10.
Danh sách sau khi biến đổi lần thứ nhất.
25 45 55 10 90.
Ta nhận thấy phần tử 90 lớn nhất được đưa về cuối danh sách, cứ tuần tự kiểm tra n lần như vậy ta sẽ được một danh sách tăng dần.
Tiếp giờ ta sẽ Mô Tả Giải Thuật Bubble Sort
C++ Code:
- Dữ liệu nhập: Danh sách n nút chưa sắp xếp.
- Dữ liệu xuất: Danh sách n nút đã sắp xếp.
- Biến tạm: doicho
- Hành động:
- Gán doicho = true;
- for(int i = 1;i < n && doicho = true;i++)
- {
- Gán doicho = flase;
- for(j = 0;i < n-1; j++)
- if(nodes[j] > nodes[j+1]))
- {
- Gán doicho = true;
- Đỗi chỗ cho hai nút tại vị trí j và j+1
- }
- }
- Kết thúc
C++ Code:
void BubbleSort(int nodes[],int n) // n la so phan tu trong mang nodes[]
void BubbleSort(int nodes[],int n) // n la so phan tu trong mang nodes[]
- {
- int temp,i,j;
- bool doicho = true;
- for(i = 1; i < n && doicho == true; i++)
- {
- doicho = false;
- for(j = 0;j < n-i; j++)
- if(nodes[j] < nodes[j+1])
- {
- doicho = true;
- temp = nodes[j];
- nodes[j] = nodes[j+1];
- nodes[j+1] = temp;
- }
- }
- }
- Swap là hàm đổi chỗ hai biến cho nhau, dùng để hoán đổi hai giá trị của hai vị trí trong mảng cần sắp xếp.
- Hàm BubbleSort là hàm nổi bọt, so sánh hai vị trí liên kề nhau, nếu không đúng tính chất (tăng dần, không tăng, giảm dần, không giảm) thì đổi chỗ
Nhận xét: Giải thuật bubble sort dễ hiểu nhưng không tối ưu vì thời gian thực hiện giải thuật dài.