Các thuật toán sắp xếp các giá trị trong mảng năm 2024

Thuật toán sắp xếp là các phương pháp sắp xếp lại một mảng gồm nhiều phần tử theo một thứ tự cụ thể như từ cao đến thấp hoặc thừ thấp đến cao. Hoặc là thứ tự bảng chữ cái.

Các thuật toán này lấy một danh sách đầu vào, xử lý nó (tức là, thực hiện một số thao tác trên nó) và tạo ra danh sách được sắp xếp.

Nếu các bạn đang muốn tìm hiểu về thuật toán sắp xếp dãy số tăng dần theo thứ tự từ thấp đến cao hoặc giảm dần từ cao nhất đến thấp nhất. Các bạn hãy tiếp tục tìm hiểu bài này. Mình sẽ giới thiệu tất cả các thuật toán sắp xếp hiện nay, và só sánh, và cách sử dụng.

Ví dụ sắp xếp dãy số: Input {5, 45, 67, 21, 10, 15} và Output theo thứ tự tăng dần {5, 10, 15, 21, 45, 67}

Ví dụ phổ biến nhất mà chúng tôi trải nghiệm hàng ngày là phân loại quần áo hoặc các mặt hàng khác trên trang web thương mại điện tử theo giá thấp nhất đến cao nhất hoặc liệt kê theo mức độ phổ biến hoặc một số đơn đặt hàng khác.

ví dụ thuật toán sắp xếp

1. Sắp xếp nhanh Quick Sort
2. Bubble Sort
3. Merge Sort
4. Sắp xếp chèn Insertion Sort
5. Sắp xếp lựa chọn Selection Sort
6. Heap Sort
7. Radix Sort
8. Bucket Sort.

Tùy theo vào độ hiệu quả, dễ dàng triển khai, hoặc tùy input mà chúng ta sử dụng các thuật toán khác nhau. Để hiểu rõ cách ứng dụng và triển khai các thuật toán sắp xếp, các nện nên tìm hiểu kỹ các bài viết ở trên để có thể lựa chọn được thuật toán hiệu quả nhất cho bài toán của các bạn.

Ngoài thuật toán tìm kiếm, trong bài học tuần này, chúng ta sẽ làm quen thêm một thuật toán quan trọng khác trong đời sống đó là thuật toán sắp xếp.

1. Định nghĩa

Thuật toán sắp xếp là thuật toán dùng để xếp lại vị trí thứ tự của các giá trị trong một tập hợp hay chuỗi dữ liệu theo thứ tự từ bé đến lớn hay lớn đến bé hay theo yêu cầu của người dùng/khách hàng. Thuật toán sắp xếp không chỉ có thể dùng với số mà còn thể dùng với kí tự.

2. Các thuật toán sắp xếp

Những thuật toán sắp xếp phổ biến:

a. Bubble Sort Algorithm (sắp xếp sủi bọt):

Thuật toán này sẽ sắp xếp các cặp số hay giá trị liền kề nhau bằng cách so sánh và hoán đổi giá trị của 2 số đó, và sẽ lặp lại cho đến khi dãy dữ liệu hoặc tập hợp đã theo thứ tự. Chúng ta có thể hình dung thuật toán sắp xếp sủi bọt bằng hình động dưới đây.

Tên của thuật toán xuất phát từ việc các số nhỏ nhất hoặc lớn nhất “sủi bọt” lên vị trí đầu trong dãy số. Thuật toán sắp xếp sủi bọt dễ sử dụng và lập trình. Tuy nhiên, thuật toán này rất không hiệu quả với dãy có nhiều số.

b. Insertion Sort Algorithm (sắp xếp chèn):

Thuật toán này hoạt động bằng cách so sánh và xếp số có giá trị nhỏ nhất hoặc lớn nhất về hướng bên trái, và lặp lại đến khi dãy số đã vào thứ tự. Chúng ta có thể hình dung thuật toán sắp xếp chèn bằng hình động dưới đây.

Thuật toán sắp xếp di chuyển một phần tử của dãy số từ phần chưa được sắp xếp và chèn vào phần đã được sắp xếp. Đó cũng chính là một phần lý do về tên gọi của thuật toán này. Chúng ta chắc đã từng một vài lần sử dụng thuật toán này để sắp xếp các lá bài trên tay khi chơi cùng bạn bè. Thuật toán sắp xếp chèn không tốn nhiều bộ nhớ và dễ sử dụng cho các dãy số có ít phần tử.

c. Selection Sort Algorithm (sắp xếp chọn lọc):

Thuật toán này sẽ liên tục chọn phần tử hay dữ liệu có giá trị nhỏ và sẽ đưa nó lên đầu, và sẽ tiếp tục lặp lại việc chọn phần tử để sắp xếp dãy số theo thứ tự tăng dần. Tương tự thuật toán có thể được sử dụng để sắp xếp dãy số theo thứ tự giảm dần bằng cách chọn phần tử có giá trị lớn để đưa lên đầu. Chính vì thế thuật toán có tên gọi là sắp xếp chọn lọc. Chúng ta có thể hình dung thuật toán sắp xếp chọn lọc bằng hình động dưới đây.

Thuật toán sắp xếp chọn lọc nhanh và hữu ích cho dãy số có nhiều phần tử. Tuy nhiên, thuật toán sắp xếp chọn lọc cũng không hiệu quả với dãy số có nhiều phần tử.

d. Merge Sort Algorithm (sắp xếp trộn):

Thuật toán này sẽ chia tập hợp hay mảng dữ liệu ra làm 2 nửa, rồi tiếp tục chia nửa các mảng nhỏ đó, rồi sắp xếp các giá trị trong các mảng nhỏ đó, và sau cùng sẽ gộp các mảng đó lại thành một mảng giá trị đã được sắp xếp. Đó cũng là lý do thuật toán có tên là sắp xếp trộn. Chúng ta có thể hình dung thuật toán bằng hình động dưới đây.

Thuật toán sắp xếp trộn hoạt động tốt với các dãy số có nhiều phần tử. Tuy nhiên thuật toán tốn nhiều dung lượng.

Ngoài ra còn có các thuật toán sắp xếp khác gồm:

• Quick Sort Algorithm
• Heap Sort Algorithm
• Counting Sort Algorithm
• Radix Sort Algorithm
• Bucket Sort Algorithm
• Shell Sort Algorithm

Không có thuận toán nào thật sự hoàn hảo, tùy vào trường hợp và lượng dữ liệu/thông tin mà thuật toán đó có thể phù hợp và sắp xếp nhanh hơn các thuật toán còn lại

3. Ứng dụng thực tế

Các thuật toán sắp xếp được ứng dụng trong nhiều lĩnh vực và công nghiệp như ngân hàng dùng để sắp xếp thống kê sổ sách tiền tệ, phân tích dữ liệu sẽ dùng thuật toán để sắp các dữ kiện theo thứ tự thích hợp để tiện cho việc xử lý và đưa ra các biểu đồ cũng như thông tin cho công ty chủ quản.

4. Cách để viết các thuật toán bằng Python

• Bubble Sort Algorithm

Pseudo Code:

for i in range of sample_list:

for j in range of sample_list:

// so sánh 2 số liền kề

if sample_list[j] > sample_list[j+1]:

// đổi vị trí 2 số đó

Ví dụ: như sắp xếp cho các bạn trong một hàng theo thứ tự từ thấp đến cao thì mình sẽ so sánh chiều cao của 2 bạn liền kề rồi mình sẽ đổi vị trí 2 bạn, ai lùn hơn thì mình đổi qua trái ai cao thì sẽ đổi qua bên phải và mình cứ lặp đi lặp lại cho đến khi hàng của mình là từ thấp đến cao.

• Insertion Sort Algorithm

Pseudo Code:

// đặt 2 giá trị

position // giá trị position để mình theo dõi vị trí của số mình sắp xếp

insert_value // giá trị số mình sắp xếp

for i in range of sample_list:

insert_value = sample_list[i]

position = i

// tìm vị trí để sắp xếp số

while position > 0 and sample_list[position – 1] > insert_value:

// hoán đổi vị trí các số

sample_list[position] = sample_list[position – 1]

position = position – 1

// bỏ số đó vào vị trí đúng

sample_list[position] = insert_value

Ví dụ: như mình sắp xếp các bạn trong một hàng theo thứ tự từ thấp đến cao thì nếu như bạn đầu tiên đã là lùn nhất rồi thì mình sẽ giữ nguyên vị trí bạn đầu tiên, sau đó mình bắt đầu so sánh như các mình làm với bubble sort nhưng thay vì mình so sánh 2 bạn một lần thì mình sẽ so sánh một bạn với tất cả các bạn ở bên tay trái để mình đưa bạn đó vào đúng vị trí, và mình cứ lặp đi lặp lại cho đến khi hàng của mình là từ thấp đến cao.

— — —

STEAM for Vietnam Foundation là tổ chức phi lợi nhuận 501(c)(3) được thành lập tại Hoa Kỳ với sứ mệnh thúc đẩy các hoạt động liên quan tới giáo dục STEAM (Science — Khoa học, Technology — Công nghệ, Engineering — Kỹ thuật, Arts — Nghệ thuật, Mathematics — Toán học) tại Việt nam. STEAM for Vietnam được thành lập và vận hành bởi đội ngũ tình nguyện viên là du học sinh và chuyên gia người Việt trên khắp thế giới.