Mi az a beillesztési rendezés C-ben?
A beszúrásos rendezésnek nevezett rendezési módszer minden egyes elemet a szomszédos elemekkel egyeztet, miközben egy tömbön keresztül ismétlődik. Az előtte lévőnél kisebb elem kerül be a rendezett altömbbe a megfelelő helyre.
A további szemléltetés kedvéért bemutattam egy példát, amelyben egy négy elemből álló tömböt vettem figyelembe egy tömbben, mint pl. arr[]= {5, 4, 60, 9} és ezt az elemet növekvő sorrendbe szeretnénk rendezni a beillesztési rendezés használatával. A következő interakciók magyarázzák a beillesztési rendezés teljes száraz futtatását:
1. iteráció
| 5 | 4 | 60 | 9 |
Most van egy tömbünk arr[5, 4, 60, 9] formátumban, a beillesztési rendezés első iterációjában először összehasonlítjuk az első két elemet, például az 5-öt és a 4-et. Mivel az arr[5] > arr[4] felcseréljük őket, hogy a tömböt növekvő sorrendbe rendezzük. Most a tömb a következő lesz:
| 4 | 5 | 60 | 9 |
2. iteráció
| 4 | 5 | 60 | 9 |
A második iterációban összehasonlítjuk a következő két elemet, mint például az arr[5] és az arr[60].
Mivel az arr[5] < arr[60], így a csere nem történik meg, mivel az már növekvő sorrendben van rendezve. Most a tömb a következő lesz:
| 4 | 5 | 60 | 9 |
3. iteráció
| 4 | 5 | 60 | 9 |
A harmadik iterációhoz hasonlóan a harmadik és negyedik elemet, mint például az arr[60] és az arr[9], párosítjuk.
Most látjuk, hogy az arr[60] > arr[9], tehát csere történik, akkor a tömb növekvő sorrendbe rendeződik.
| 4 | 5 | 9 | 60 |
Így működik a beillesztési rendezés C-ben, amely könnyen rendezi a tömbelemeket növekvő vagy csökkenő sorrendben.
Beillesztési folyamatábra
A következő a beillesztési rendezés algoritmusának folyamatábrája:
Beillesztési rendezés megvalósítási példája C-ben
Először is szükségünk van egy olyan elemek gyűjteményére, amelyeket csökkenő és növekvő sorrendbe kell rendezni a beillesztési rendezési metódus felépítéséhez C-ben. Tegyük fel, hogy a példa céljaira számok tömbjével van dolgunk {5, 4, 60, 9} :
#includeüres insertionsort_ascending ( int arr1 [ ] , int n ) {
int én , j , a kulcsom ;
A //for ciklus az i értékek iterálására szolgál 1-től i
számára ( én = 1 ; én < n ; én ++ ) {
a kulcsom = arr1 [ én ] ;
j = én - 1 ;
míg ( j >= 0 && arr1 [ j ] > a kulcsom ) {
arr1 [ j + 1 ] = arr1 [ j ] ;
j = j - 1 ;
}
arr1 [ j + 1 ] = a kulcsom ;
}
}
üres insertionsort_descending ( int arr2 [ ] , int m ) {
int én , j , a kulcsom ;
//egy másik for ciklus jön létre az i értékek iterálására 1-től i
számára ( én = 1 ; én < m ; én ++ ) {
a kulcsom = arr2 [ én ] ;
j = én - 1 ;
míg ( j >= 0 && arr2 [ j ] < a kulcsom ) {
arr2 [ j + 1 ] = arr2 [ j ] ;
j = j - 1 ;
}
arr2 [ j + 1 ] = a kulcsom ;
}
}
int fő- ( ) {
//Beszúrás-Rendezés csökkenő sorrendben
int my_arr [ ] = { 5 , 4 , 60 , 9 } ; //inicializál egy my_arr[]-t, amelynek négy értéke van
int m = mérete ( my_arr ) / mérete ( my_arr [ 0 ] ) ;
insertionsort_descending ( my_arr , m ) ;
printf ( 'Rendezett tömb csökkenő sorrendben: ' ) ;
számára ( int én = 0 ; én < m ; én ++ )
printf ( '%d' , my_arr [ én ] ) ;
printf ( ' \n ' ) ;
//Beszúrás-Rendezés növekvő sorrendben
int n = mérete ( my_arr ) / mérete ( my_arr [ 0 ] ) ;
insertionsort_ascending ( arr2 , n ) ;
printf ( 'Rendezett tömb növekvő sorrendben: ' ) ;
számára ( int én = 0 ; én < n ; én ++ )
printf ( '%d' , my_arr [ én ] ) ;
printf ( ' \n ' ) ;
Visszatérés 0 ;
}
Ebben a kódban két módszer insertionsort_descending() , és insertionsort_ascending() vegyük a tömb értékeit my_arr[] . A kód ezután a hurokhoz a tömb elemei közötti iterációhoz.
Mindkét függvényt meghívjuk a főfüggvényben, miután a tömböket csökkenő és növekvő sorrendbe rendezték. Ezt követően a for ciklusok segítségével nyomtatjuk ki a rendezett tömböt.
Amikor ezt a programot futtatjuk, a várt kimenet alább kerül:
Következtetés
A beillesztési rendezés gyors és egyszerű módja a tömbök csökkenő vagy növekvő sorrendben történő rendezésének. Kis adatkészletek esetén ez a rendezési technika jól teljesít. Amint az a fenti útmutatóból látható, egyszerűen megvalósítható egy példa egy C programra, hogy könnyen megértse a beszúrási rendezést csökkenő és növekvő sorrendben.