Sắp xếp chèn trong C là gì?
Phương pháp sắp xếp được gọi là sắp xếp chèn khớp mọi phần tử đơn lẻ với các phần tử liền kề khi nó lặp qua một mảng. Phần tử nhỏ hơn phần tử trước nó được chèn vào mảng con đã sắp xếp tại vị trí thích hợp.
Để minh họa thêm, tôi đã trình bày một ví dụ trong đó tôi đã xem xét một mảng gồm bốn phần tử trong một mảng chẳng hạn như mảng[]= {5, 4, 60, 9} và chúng tôi muốn sắp xếp phần tử này theo thứ tự tăng dần bằng cách sử dụng sắp xếp chèn. Các tương tác sau đây giải thích quá trình sắp xếp chèn khô hoàn toàn:
lặp lại 1
| 5 | 4 | 60 | 9 |
Bây giờ chúng ta có một mảng là mảng[5, 4, 60, 9], trong lần lặp đầu tiên của sắp xếp chèn, trước tiên chúng ta so sánh hai phần tử đầu tiên chẳng hạn như 5 và 4, Vì mảng[5] là > mảng[4] nên chúng tôi hoán đổi chúng để sắp xếp mảng theo thứ tự tăng dần. Bây giờ, mảng sẽ là:
| 4 | 5 | 60 | 9 |
lặp lại 2
| 4 | 5 | 60 | 9 |
Trong lần lặp thứ hai, chúng tôi so sánh hai phần tử tiếp theo, chẳng hạn như mảng[5] với mảng[60].
Vì mảng[5] < mảng[60] nên việc hoán đổi không xảy ra vì nó đã được sắp xếp theo thứ tự tăng dần. Bây giờ, mảng trở thành:
| 4 | 5 | 60 | 9 |
lặp lại 3
| 4 | 5 | 60 | 9 |
Như trong lần lặp thứ ba, chúng tôi khớp các phần tử thứ ba và thứ tư như mảng[60] với mảng[9].
Bây giờ, chúng ta thấy rằng mảng[60] > mảng[9] nên việc hoán đổi xảy ra, khi đó mảng sẽ sắp xếp theo thứ tự tăng dần.
| 4 | 5 | 9 | 60 |
Đây là cách sắp xếp chèn hoạt động trong C giúp sắp xếp một phần tử mảng dễ dàng theo thứ tự tăng dần hoặc giảm dần.
Lưu đồ sắp xếp chèn
Sau đây là lưu đồ của thuật toán sắp xếp chèn:
Thực hiện ví dụ sắp xếp chèn trong C
Trước tiên, chúng tôi yêu cầu một tập hợp các phần tử cần được sắp xếp theo thứ tự giảm dần và tăng dần để xây dựng phương thức sắp xếp chèn trong C. Giả sử cho mục đích của ví dụ này là chúng tôi đang xử lý một mảng số {5, 4, 60, 9} :
#includekhoảng trống insertionsort_ascending ( int mảng1 [ ] , int N ) {
int Tôi , j , chìa khóa của tôi ;
//vòng lặp for được sử dụng để lặp lại các giá trị i từ 1 đến i
vì ( Tôi = 1 ; Tôi < N ; Tôi ++ ) {
chìa khóa của tôi = mảng1 [ Tôi ] ;
j = Tôi - 1 ;
trong khi ( j >= 0 && mảng1 [ j ] > chìa khóa của tôi ) {
mảng1 [ j + 1 ] = mảng1 [ j ] ;
j = j - 1 ;
}
mảng1 [ j + 1 ] = chìa khóa của tôi ;
}
}
khoảng trống insertionsort_descending ( int mảng2 [ ] , int tôi ) {
int Tôi , j , chìa khóa của tôi ;
// một vòng lặp for khác được tạo để lặp lại các giá trị i từ 1 đến i
vì ( Tôi = 1 ; Tôi < tôi ; Tôi ++ ) {
chìa khóa của tôi = mảng2 [ Tôi ] ;
j = Tôi - 1 ;
trong khi ( j >= 0 && mảng2 [ j ] < chìa khóa của tôi ) {
mảng2 [ j + 1 ] = mảng2 [ j ] ;
j = j - 1 ;
}
mảng2 [ j + 1 ] = chìa khóa của tôi ;
}
}
int chủ yếu ( ) {
// Chèn-Sắp xếp theo thứ tự giảm dần
int my_arr [ ] = { 5 , 4 , 60 , 9 } ; //khởi tạo một my_arr[] có 4 giá trị
int tôi = kích thước của ( my_arr ) / kích thước của ( my_arr [ 0 ] ) ;
insertionsort_descending ( my_arr , tôi ) ;
bản inf ( 'Mảng đã sắp xếp theo thứ tự giảm dần: ' ) ;
vì ( int Tôi = 0 ; Tôi < tôi ; Tôi ++ )
bản inf ( '%d' , my_arr [ Tôi ] ) ;
bản inf ( ' \N ' ) ;
//Chèn-Sắp xếp tăng dần
int N = kích thước của ( my_arr ) / kích thước của ( my_arr [ 0 ] ) ;
insertionsort_ascending ( mảng2 , N ) ;
bản inf ( 'Đã sắp xếp mảng theo thứ tự tăng dần: ' ) ;
vì ( int Tôi = 0 ; Tôi < N ; Tôi ++ )
bản inf ( '%d' , my_arr [ Tôi ] ) ;
bản inf ( ' \N ' ) ;
trở lại 0 ;
}
Trong mã này, hai phương pháp insertionsort_descending() , Và insertionsort_ascending() lấy các giá trị mảng của my_arr[] . Đoạn mã sau đó sử dụng một cho vòng lặp để lặp qua các phần tử của mảng.
Chúng ta gọi cả hai hàm trong hàm chính khi chúng đã sắp xếp các mảng theo thứ tự giảm dần và tăng dần. Sau đó, vòng lặp for được sử dụng để in mảng đã sắp xếp.
Khi chúng tôi chạy chương trình này, đầu ra dự kiến được đặt bên dưới:
Phần kết luận
Sắp xếp chèn là một cách nhanh chóng và dễ dàng để sắp xếp một mảng theo thứ tự giảm dần hoặc tăng dần. Đối với các tập dữ liệu nhỏ, kỹ thuật sắp xếp này hoạt động tốt. Như bạn có thể thấy trong hướng dẫn ở trên, thật đơn giản để triển khai một ví dụ về chương trình C để dễ dàng hiểu được sắp xếp chèn theo thứ tự giảm dần cũng như tăng dần.