Có một số thuật toán cơ bản để giải quyết vấn đề sắp xếp một mảng. Một trong những cách nổi tiếng nhất trong số đó là sắp xếp chèn. Do tính rõ ràng, đơn giản nhưng hiệu quả thấp nên phương pháp này được sử dụng chủ yếu trong dạy học lập trình. Nó cho phép bạn hiểu các cơ chế sắp xếp cơ bản.
Mô tả thuật toán
Bản chất của thuật toán sắp xếp chèn là một phân đoạn có thứ tự đúng được hình thành bên trong mảng ban đầu. Từng phần tử được so sánh từng phần một với phần đã kiểm tra và được chèn vào đúng vị trí. Do đó, sau khi lặp lại tất cả các phần tử, chúng sẽ sắp xếp theo đúng thứ tự.
Thứ tự chọn các phần tử có thể là bất kỳ, có thể chọn tùy ý hoặc theo thuật toán nào đó. Thông thường, liệt kê tuần tự được sử dụng từ đầu mảng, nơi tạo ra một phân đoạn có thứ tự.
Bắt đầu sắp xếp có thể giống như sau:
- Lấy phần tử đầu tiên của mảng.
- Vì không có gì để so sánh với nó, hãy lấy chính phần tử đó theo thứ tựtrình tự.
- Đến mục thứ hai.
- So sánh nó với cái đầu tiên dựa trên quy tắc sắp xếp.
- Nếu cần, hãy hoán đổi các phần tử ở các vị trí.
- Lấy hai phần tử đầu tiên làm chuỗi có thứ tự.
- Đến mục thứ ba.
- So sánh nó với cái thứ hai, hoán đổi nếu cần.
- Nếu thay thế được thực hiện, hãy so sánh nó với cái đầu tiên.
- Lấy ba phần tử làm chuỗi có thứ tự.
Và cứ tiếp tục như vậy cho đến hết mảng ban đầu.
Sắp xếp chèn trong cuộc sống thực
Để rõ ràng, cần đưa ra một ví dụ về cách cơ chế phân loại này được sử dụng trong cuộc sống hàng ngày.
Lấy ví dụ như một chiếc ví. Những tờ tiền trăm, năm trăm nghìn đô la nằm ngổn ngang trong ngăn đựng tiền giấy. Đây là một mớ hỗn độn, trong một mớ hỗn độn như vậy, rất khó để tìm ra ngay mẩu giấy thích hợp. Mảng tiền giấy phải được sắp xếp.
Đầu tiên là tờ tiền 1000 rúp, và ngay sau đó - 100. Chúng tôi lấy một trăm và đặt nó ở phía trước. Đồng thứ ba liên tiếp là 500 rúp, vị trí thích hợp cho nó là từ một trăm đến một nghìn.
Theo cách tương tự, chúng tôi sắp xếp các thẻ nhận được khi chơi trò "Tài xỉu" để điều hướng chúng dễ dàng hơn.
Các toán tử và chức năng trợ giúp
Phương thức sắp xếp chèn nhận đầu vào là một mảng ban đầu được sắp xếp, một hàm so sánh và, nếu cần, một hàm xác định quy tắc liệt kê các phần tử. Thường được sử dụng thay thếcâu lệnh lặp thông thường.
Phần tử đầu tiên tự nó là một tập hợp có thứ tự, vì vậy việc so sánh bắt đầu từ phần tử thứ hai.
Thuật toán thường sử dụng hàm trợ giúp để trao đổi hai giá trị (hoán đổi). Nó sử dụng một biến tạm thời bổ sung, làm tiêu tốn bộ nhớ và làm chậm mã một chút.
Một giải pháp thay thế là thay đổi khối lượng một nhóm phần tử và sau đó chèn nhóm phần tử hiện tại vào không gian trống. Trong trường hợp này, quá trình chuyển đổi sang phần tử tiếp theo xảy ra khi phép so sánh cho kết quả dương tính, cho biết thứ tự chính xác.
Ví dụ thực hiện
Việc triển khai cụ thể phần lớn phụ thuộc vào ngôn ngữ lập trình được sử dụng, cú pháp và cấu trúc của nó.
Triển khai C cổ điển bằng cách sử dụng một biến tạm thời để trao đổi các giá trị:
int i, j, temp; for (i=1; i=0; j--) {if (array [j] < temp) break; array [j + 1]=array [j]; array [j]=temp; }}
PHP Thực hiện:
function insert_sort (& $ a) {for ($ i=1; $ i=0 && $ a [$ j] > $ x; $ j--) {$ a [$ j + 1]=$ a [$ j]; } $ a [$ j + 1]=$ x; }}
Ở đây, trước tiên, tất cả các phần tử không phù hợp với điều kiện sắp xếp sẽ được chuyển sang bên phải, sau đó phần tử hiện tại được chèn vào vùng trống.
Mã Java sử dụng vòng lặp while:
public static void inserttionSort (int arr) {for (int i=1; i=0 && arr [presKey] > currElem) {arr [prevKey + 1]=arr [presKey]; arr [presKey]=currElem; trước đây--; }}}
Ý nghĩa chung của đoạn mã vẫn không thay đổi: mỗi phần tử của mảng được so sánh tuần tự với các phần tử trước đó và được hoán đổi với chúng nếu cần.
Thời gian chạy ước tính
Rõ ràng, trong trường hợp tốt nhất, đầu vào của thuật toán sẽ là một mảng đã được sắp xếp theo đúng thứ tự. Trong tình huống này, thuật toán sẽ chỉ cần kiểm tra từng phần tử để đảm bảo rằng nó ở đúng vị trí mà không cần thực hiện trao đổi. Do đó, thời gian chạy sẽ phụ thuộc trực tiếp vào độ dài của mảng ban đầu O (n).
Đầu vào trường hợp xấu nhất là một mảng được sắp xếp theo thứ tự ngược lại. Điều này sẽ yêu cầu một số lượng lớn các hoán vị, hàm thời gian chạy sẽ phụ thuộc vào số phần tử được bình phương.
Có thể tính số hoán vị chính xác cho một mảng hoàn toàn không có thứ tự bằng công thức:
n(n-1) / 2
với n là độ dài của mảng ban đầu. Do đó, sẽ cần 4950 hoán vị để sắp xếp 100 phần tử theo đúng thứ tự.
Phương pháp chèn rất hiệu quả để sắp xếp các mảng nhỏ hoặc được sắp xếp một phần. Tuy nhiên, không nên áp dụng nó ở mọi nơi do tính toán phức tạp cao.
Thuật toán được sử dụng như một phép bổ trợ trong nhiều phương pháp sắp xếp phức tạp hơn.
Sắp xếp các giá trị bằng nhau
Thuật toán chèn thuộc về cái gọi là các loại ổn định. Nó có nghĩa là,rằng nó không hoán đổi các phần tử giống hệt nhau, nhưng giữ nguyên thứ tự ban đầu của chúng. Trong nhiều trường hợp, chỉ số ổn định rất quan trọng để đặt hàng đúng.
Trên đây là một ví dụ trực quan tuyệt vời về sắp xếp chèn trong một điệu nhảy.
