Hãy xem xét những con số sau:
50 60 30 10 80 70 20 40
Nếu danh sách này được sắp xếp theo thứ tự tăng dần, nó sẽ là:
10 20 30 40 50 60 70 80
Nếu nó được sắp xếp theo thứ tự giảm dần, nó sẽ là:
80 70 60 50 40 30 20 10
Sắp xếp chèn là một thuật toán sắp xếp được sử dụng để sắp xếp danh sách theo thứ tự tăng dần hoặc theo thứ tự giảm dần. Bài viết này chỉ đề cập đến việc sắp xếp theo thứ tự tăng dần. Sắp xếp theo thứ tự giảm dần tuân theo cùng một logic được đưa ra trong tài liệu này. Mục đích của bài viết này là giải thích cách sắp xếp chèn. Lập trình được thực hiện trong ví dụ sau trong C. Sắp xếp chèn được giải thích ở đây bằng cách sử dụng một mảng.
Thuật toán sắp xếp chèn
Một danh sách không được sắp xếp được đưa ra. Mục đích là để sắp xếp danh sách theo thứ tự tăng dần bằng cách sử dụng cùng một danh sách. Sắp xếp một mảng không được sắp xếp bằng cách sử dụng cùng một mảng được cho là sắp xếp tại chỗ. Việc lập chỉ mục dựa trên số không được sử dụng ở đây. Các bước thực hiện như sau:
-
- Danh sách được quét từ đầu.
- Trong khi quá trình quét đang diễn ra, bất kỳ số nào nhỏ hơn số tiền nhiệm của nó sẽ được hoán đổi với người tiền nhiệm của nó.
- Việc hoán đổi này tiếp tục dọc theo danh sách, cho đến khi không thể hoán đổi được nữa.
- Khi quá trình quét kết thúc, việc phân loại đã hoàn tất.
Hình minh họa sắp xếp chèn
Khi đối mặt với sự phức tạp về thời gian, đó là trường hợp xấu nhất thường được xem xét. Sự sắp xếp tồi tệ nhất cho danh sách trước đó là:
80 70 60 50 40 30 20 10
Có tám phần tử có chỉ số từ 0 đến 7.
Tại chỉ số 0, quá trình quét chuyển đến 80. Đây là một chuyển động. Một chuyển động này là một hoạt động. Có tổng cộng một hoạt động cho đến nay (một chuyển động, không so sánh và không hoán đổi). Kết quả là:
| 80 70 60 50 40 30 20 10
Ở chỉ số một, có một sự di chuyển đến 70. 70 được so sánh với 80. 70 và 80 được hoán đổi. Một chuyển động là một hoạt động. Một so sánh cũng là một hoạt động. Một hoán đổi cũng là một hoạt động. Phần này cung cấp ba hoạt động. Cho đến nay có tổng cộng bốn phép toán (1 + 3 = 4). Kết quả là như sau:
70 | 80 60 50 40 30 20 10
Ở chỉ số hai, có một sự di chuyển đến 60. 60 được so sánh với 80, sau đó 60 và 80 được đổi chỗ cho nhau. 60 được so sánh với 70, sau đó 60 và 70 được hoán đổi. Một chuyển động là một hoạt động. Hai phép so sánh là hai phép toán. Hai hoán đổi là hai hoạt động. Phần này cung cấp năm hoạt động. Có tổng cộng chín hoạt động cho đến nay (4 + 5 = 9). Kết quả là như sau:
60 70 | 80 50 40 30 20 10
Ở chỉ số ba, có sự di chuyển đến 50. 50 được so sánh với 80, sau đó 50 và 80 được hoán đổi. 50 được so sánh với 70, sau đó 50 và 70 được hoán đổi. 50 được so sánh với 60, sau đó 50 và 60 được hoán đổi. Một chuyển động là một hoạt động. Ba phép so sánh là ba phép toán. Ba lần hoán đổi là ba hoạt động. Phần này cung cấp bảy hoạt động. Có tổng cộng mười sáu phép toán cho đến nay (9 + 7 = 16). Kết quả là như sau:
50 60 70 | 80 40 30 20 10
Ở chỉ số bốn, có một sự dịch chuyển đến 40. 40 được so sánh với 80, sau đó 40 và 80 được hoán đổi. 40 được so sánh với 70, sau đó 40 và 70 được hoán đổi. 40 được so sánh với 60, sau đó 40 và 60 được đổi chỗ cho nhau. 40 được so sánh với 50, sau đó 40 và 50 được hoán đổi. Một chuyển động là một hoạt động. Bốn phép so sánh là bốn phép toán. Bốn hoán đổi là bốn hoạt động. Phần này cung cấp chín hoạt động. Có tổng cộng 25 phép toán cho đến nay (16 + 9 = 25). Kết quả là như sau:
40 50 60 70 80 | 30 20 10
Ở chỉ số năm, có sự di chuyển đến 30. 30 được so sánh với 80, sau đó 30 và 80 được hoán đổi. 30 được so sánh với 70, sau đó 30 và 70 được hoán đổi. 30 được so sánh với 60, sau đó 30 và 60 được hoán đổi. 30 được so sánh với 50, sau đó 30 và 50 được hoán đổi. 30 được so sánh với 40, sau đó 30 và 40 được hoán đổi. Một chuyển động là một hoạt động. Năm phép so sánh là năm phép toán. Năm lần hoán đổi là năm hoạt động. Phần này cung cấp mười một hoạt động. Có tổng cộng ba mươi sáu phép toán cho đến nay (25 + 11 = 36). Kết quả là như sau:
30 40 50 60 70 80 | 20 10
Ở chỉ số sáu, có một sự di chuyển đến 20. 20 được so sánh với 80, sau đó 20 và 80 được hoán đổi. 20 được so sánh với 70, sau đó 20 và 70 được hoán đổi. 20 được so sánh với 60, sau đó 20 và 60 được hoán đổi. 20 được so sánh với 50, sau đó 20 và 50 được hoán đổi. 20 được so sánh với 40, sau đó 20 và 40 được hoán đổi. 20 được so sánh với 30, sau đó 20 và 30 được hoán đổi. Một chuyển động là một hoạt động. Sáu phép so sánh là sáu phép toán. Sáu lần hoán đổi là sáu hoạt động. Phần này cung cấp mười ba hoạt động. Có tổng cộng bốn mươi chín hoạt động cho đến nay (36 + 13 = 49). Kết quả là như sau:
20 30 40 50 60 70 80 | 10
Ở chỉ số bảy, có một sự chuyển động đến 10. 10 được so sánh với 80, sau đó 10 và 80 được hoán đổi. 10 được so sánh với 70, sau đó 10 và 70 được hoán đổi. 10 được so sánh với 60, sau đó 10 và 60 được hoán đổi. 10 được so sánh với 50, sau đó 10 và 50 được hoán đổi. 10 được so sánh với 30, sau đó 10 và 40 được hoán đổi. 10 được so sánh với 30, sau đó 10 và 30 được hoán đổi. 10 được so sánh với 20, sau đó 10 và 20 được đổi chỗ cho nhau. Một chuyển động là một hoạt động. Bảy phép so sánh là bảy phép toán. Bảy lần hoán đổi là bảy hoạt động. Phần này cung cấp mười lăm phép toán. Có tổng cộng sáu mươi bốn hoạt động cho đến nay (49 + 15 = 64). Kết quả là như sau:
10 20 30 40 50 60 70 80 10 |
Công việc đã hoàn thành! 64 hoạt động đã được tham gia.
64 = 8 x 8 = 8 hai
Độ phức tạp về thời gian để sắp xếp chèn
Nếu có n phần tử để sắp xếp với Insertion Sort, số phép toán tối đa có thể thực hiện sẽ là n2, như đã trình bày trước đây. Độ phức tạp của Thời gian Sắp xếp Chèn là:
Trên hai )
Điều này sử dụng ký hiệu Big-O. Kí hiệu Big-O bắt đầu bằng chữ O in hoa, theo sau là dấu ngoặc đơn. Bên trong dấu ngoặc đơn là biểu thức cho số lượng phép toán lớn nhất có thể.
Mã hóa bằng C
Vào lúc bắt đầu quét, phần tử đầu tiên không thể thay đổi vị trí của nó. Chương trình về cơ bản như sau:
#includevoid inserttionSort ( int A [ ] , int N ) {
vì ( int tôi = 0 ; tôi < N; i ++ ) {
int j = i;
trong khi ( Một [ j ] < Một [ j- 1 ] && j- 1 > = 0 ) {
int temp = A [ j ] ; Một [ j ] = A [ j- 1 ] ; Một [ j- 1 ] = tạm thời; // tráo đổi
j--;
}
}
}
Định nghĩa hàm insertSort () sử dụng thuật toán như được mô tả. Lưu ý các điều kiện cho vòng lặp while. Một chức năng chính C phù hợp cho chương trình này là:
{
int n = số 8 ;
int A [ ] = { năm mươi , 60 , 30 , 10 , 80 , 70 , hai mươi , 40 } ;
sắp xếp chèn ( Một ) ;
vì ( int tôi = 0 ; tôi < N; i ++ ) {
printf ( '%tôi ' , MỘT [ tôi ] ) ;
}
printf ( ' \N ' ) ;
trở về 0 ;
}
Sự kết luận
Độ phức tạp về thời gian cho Sắp xếp chèn được cho là:
Trên hai )
Người đọc có thể đã nghe nói về độ phức tạp thời gian trong trường hợp xấu hơn, độ phức tạp thời gian trong trường hợp trung bình và độ phức tạp thời gian trong trường hợp tốt nhất. Các biến thể này của Độ phức tạp thời gian sắp xếp chèn được thảo luận trong bài viết tiếp theo trên trang web của chúng tôi.