Sắp xếp được dữ liệu theo các trật tự và tiêu chí khác nhau
1. Mục tiêu
- Liệt kê được các trường hợp áp dụng của thuật toán sắp xếp
- Trình bày được thuật toán sắp xếp Nổi bọt
- Cài đặt được thuật toán sắp xếp Nổi bọt
- Trình bày được thuật toán sắp xếp Chọn
- Cài đặt được thuật toán sắp xếp Chọn
- Trình bày được thuật toán sắp xếp Chèn
- Cài đặt được thuật toán sắp xếp Chèn
- Phân biệt được độ phức tạp của các thuật toán sắp xếp để có lựa chọn phù hợp
2. Giới thiệu
Sắp xếp là thao tác thay đổi vị trí của các phần tử trong một danh sách để thoả mãn một tiêu chí nhất định. Chúng ta thường gặp các danh sách có trật tự, chẳng hạn danh sách thí sinh dự thi trong một kỳ thi Đại học được sắp xếp theo tên, danh sách các quốc gia theo độ lớn của diện tích, danh sách khách hàng theo tổng giá trị hợp đồng, v.v. Để thực hiện được thao tác thay đổi vị trí của các phần tử một cách hiệu quả, chúng ta sẽ cần nghiên cứu nhiều thuật toán sắp xếp khác nhau.
Độ phức tạp của một thuật toán sắp xếp phụ thuộc vào số lượng phép so sánh và số lượng phép hoán vị cần phải thực hiện. Tối ưu hóa hai đại lượng này chính là mục tiêu của các thuật toán sắp xếp. Có nhiều thuật toán sắp xếp khác nhau, tùy thuộc vào kích thước và cách phân phối của các phần tử trong danh sách đầu vào mà mỗi loại thuật toán thể hiện một ưu thế riêng.
Kết thúc chương này, chúng ta có thể lựa chọn triển khai một số thuật toán sắp xếp khác nhau để phù hợp với các tình huống cụ thể. Chúng ta sẽ khảo sát 3 thuật toán cơ bản bao gồm: Sắp xếp Nổi bọt, Sắp xếp Chèn, Sắp xếp Chọn.
3. Thuật toán sắp xếp nổi bọt
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) cho nhau, việc đổi chỗ này được lặp đi lặp lại cho đến khi không còn phần tử nào đứng không đúng thứ tự.
Có thể tiến hành theo hướng 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.
Giải thuật này không thích hợp sử dụng với các tập dữ liệu lớn khi mà độ phức tạp trong trường hợp xấu nhất và trường hợp trung bình là Ο(n2) với n là số phần tử.
Giải thuật sắp xếp nổi bọt là giải thuật chậm nhất trong số các giải thuật sắp xếp cơ bản. Giải thuật này còn chậm hơn giải thuật đổi chỗ trực tiếp mặc dù số lần so sánh bằng nhau, nhưng do đổi chỗ hai phần tử kề nhau nên số lần đổi chỗ nhiều hơn.
Thuật toán này có tên gọi là “nổi bọt” vì hình tượng các giá trị nhỏ hơn (trong trường hợp sắp xếp giảm dần) hoặc lớn hơn (trong trường hợp sắp xếp tăng dần) lần lượt nổi lên phía trên của danh sách.
Giải thuật
Sắp xếp từ trên xuống
Giả sử dãy cần sắp xếp có n phần tử, trật tự sắp xếp là tăng dần. Khi tiến hành từ trên xuống, ta so sánh hai phần tử đầu tiên, 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.
Ví dụ: Để sắp xếp 6 phần tử (2 9 5 4 8 1) theo trật tự tăng dần. Chúng ta so sánh hai phần tử đầu tiên là 2 và 9, chúng đã đúng trật tự cho nên không cần hoán đổi gì cả. Tiếp theo chúng ta so sánh hai phần tử là 9 và 5, chúng đang không ở đúng trật tự (5 phải đứng trước 9) cho nên chúng ta phải hoán đổi vị trí của 2 phần tử này. Tiếp theo chúng ta so sánh hai phần tử là 9 và 4, phải hoán đổi vị trí của chúng. Tiếp theo chúng ta so sánh hai phần tử 9 và 8, phải hoán đổi vị trí của chúng. Tiếp theo chúng ta so sánh hai phần tử 9 và 1, phải hoán đổi vị trí của chúng.
Kết thúc lượt thứ nhất, số 9 đã được “nổi” lên trên cùng. Chúng ta sẽ thực hiện lượt thứ hai với 5 phần tử còn lại là (2 5 4 8 1). Kết thúc lượt thứ hai thì số 8 sẽ được nổi lên. Và cứ như vậy cho đến khi tất cả các phần tử đứng đúng ở vị trí của nó.
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 vị 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.
Mã giả
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 (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
endif
endfor
endfor
endprocedure
Sắp xếp từ dưới lên
procedure bubble_sort2(list L, number n) //n=listsize
For number i from 1 to 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
Cài đặt thuật toán sắp xếp nổi bọt
Hàm bubbleSort()
1. function bubbleSort(items) {
2. let length = items.length;
3. for (let i = 0; i < length; i++) {
4. for (let j = 0; j < (length - i - 1); j++) {
5. if (items[j] > items[j + 1]) {
6. let tmp = items[j];
7. items[j] = items[j + 1];
8. items[j + 1] = tmp;
9. }
10. }
11. }
12. }
Xem tiếp>> Chuong 8 Thuat toan sap xep chen
Có thể bạn quan tâm>> Cam nang lap trinh can ban danh cho nguoi moi bat dau
