Các thuật toán sắp xếp: Lựa chọn, Nổi bọt, Chèn, Gộp

Bạn đã bao giờ nghe về các thuật toán sắp xếp mảng chưa? Trong bài viết này, chúng ta sẽ cùng tìm hiểu về các thuật toán sắp xếp như Lựa chọn, Nổi bọt, Chèn và Gộp. Những thuật toán này giúp bạn sắp xếp một mảng các phần tử theo thứ tự tăng dần một cách hiệu quả. Hãy cùng bắt đầu!

Lựa chọn (Selection Sort)

Thuật toán Lựa chọn sắp xếp một mảng n phần tử bằng cách thực hiện các bước sau:

1. Xét phần tử thứ i (bắt đầu từ i = 0)
2. Tìm phần tử nhỏ nhất trong mảng từ vị trí i đến n-1
3. Hoán đổi phần tử nhỏ nhất với phần tử thứ i
4. Tăng i lên 1
5. Lặp lại bước 2 với phần tử i+1 và mảng từ i+1 đến n-1
6. Dừng lại khi i == n-1

Dưới đây là một ví dụ minh họa cho thuật toán Lựa chọn:

Ví dụ: Sắp xếp mảng arr[] = [4, 1, 2, 3, 5]

• Lần lượt xét từ vị trí arr[0] đến arr[4], ta thấy rằng 1 là phần tử nhỏ nhất => hoán đổi arr[0]=4 với arr[1]=1. Kết quả là arr[] = [1, 4, 2, 3, 5]
• Tiếp tục xét từ vị trí arr[1] đến arr[4], ta thấy rằng 2 là phần tử nhỏ nhất => hoán đổi arr[1]=4 với arr[2]=2. Kết quả là arr[] = [1, 2, 4, 3, 5]
• Tiếp tục xét từ vị trí arr[2] đến arr[4], ta thấy rằng 3 là phần tử nhỏ nhất => hoán đổi arr[2]=4 với arr[3]=3. Kết quả là arr[] = [1, 2, 3, 4, 5]
• Cuối cùng, chỉ còn lại một phần tử duy nhất là arr[4] và chắc chắn là lớn nhất. Do đó, không cần xét nữa. Kết quả cuối cùng là mảng đã được sắp xếp: arr[] = [1, 2, 3, 4, 5]

Nổi bọt (Bubble Sort)

Thuật toán Nổi bọt sắp xếp một mảng n phần tử bằng cách lặp qua n lần và thực hiện các bước sau đây trong lần lặp thứ i:

1. Kiểm tra các phần tử từ 0 đến n-i (ví dụ: lần lặp đầu tiên kiểm tra từ 0 đến n-1)
2. So sánh hai phần tử liền kề j và j+1
3. Nếu phần tử j lớn hơn phần tử j+1, hoán đổi chúng
4. Lặp lại bước 1 đến bước 3

Đây là cách thuật toán Nổi bọt hoạt động:

• Trong lần lặp đầu tiên, phần tử lớn nhất sẽ nổi lên cuối dãy (vị trí n-1)
• Trong lần lặp thứ 2, phần tử lớn nhất còn lại sẽ nổi lên vị trí n-2
• Tiếp tục cho đến khi được một dãy mảng đã sắp xếp

Thuật toán Nổi bọt như việc những bong bóng nổi lên mặt nước, từng phần tử sẽ được sắp xếp từ phần tử lớn nhất đến phần tử nhỏ nhất.

Chèn (Insert Sort)

Thuật toán Chèn sắp xếp mảng n phần tử như việc xếp bài trong khi chơi bài. Chúng ta sẽ rút từng lá bài một và xếp chúng vào vị trí phù hợp. Các bước để thực hiện thuật toán này như sau:

1. Duyệt qua từng phần tử trong mảng
2. Đặt key là giá trị của phần tử đang xét (giả sử là phần tử j)
3. Lần lượt so sánh giá trị của key với các phần tử đứng trước j
4. Nếu key nhỏ hơn phần tử arr[i], nhích phần tử so sánh lên 1 ô (tức là nhích arr[i] lên thành arr[i+1]) để mở chỗ cho key
5. Nếu key lớn hơn phần tử arr[i], đặt key vào vị trí arr[i+1]
6. Lặp lại cho tất cả n phần tử trong mảng

Gộp (Merge Sort)

Uploading...

Kết luận

Đó là một số thuật toán sắp xếp thông dụng như Lựa chọn, Nổi bọt, Chèn và Gộp. Mỗi thuật toán có cách hoạt động và ý nghĩa riêng. Việc hiểu và áp dụng chúng sẽ giúp bạn sắp xếp một mảng một cách hiệu quả. Nếu bạn muốn tìm hiểu thêm về các thuật toán khác như Heap Sort, Radix Sort, Counting Sort, Bucket Sort, Shell Sort, Comb Sort, Pigeonhole Sort và Cycle Sort, hãy tham khảo tại greeksforgreeks.org.

Hãy sử dụng những thuật toán này để giải quyết các vấn đề sắp xếp mảng trong công việc của mình. Chúc bạn thành công!