Mikä on lisäyslajittelu C:ssä?
Lajittelumenetelmä, jota kutsutaan lisäyslajitteluksi, sovittaa jokaisen yksittäisen elementin vierekkäisten elementtien kanssa, kun se toistuu taulukossa. Pienempi elementti kuin sitä edeltävä elementti lisätään lajiteltuun aliryhmään sopivaan paikkaan.
Havainnollistaakseni olen osoittanut esimerkin, jossa olen tarkastellut neljän elementin taulukkoa taulukossa, kuten arr[]= {5, 4, 60, 9} ja haluamme lajitella tämän elementin nousevaan järjestykseen käyttämällä lisäyslajittelua. Seuraavat vuorovaikutukset selittävät lisäyslajittelun täydellisen kuivaajon:
Iteraatio 1
| 5 | 4 | 60 | 9 |
Meillä on taulukko muodossa arr[5, 4, 60, 9] nyt, lisäyslajittelun ensimmäisessä iteraatiossa verrataan ensin kahta ensimmäistä elementtiä, kuten 5 ja 4. Koska arr[5] on > arr[4], niin Vaihdamme ne lajitellaksemme taulukon nousevaan järjestykseen. Nyt matriisi tulee olemaan:
| 4 | 5 | 60 | 9 |
Iteraatio 2
| 4 | 5 | 60 | 9 |
Toisessa iteraatiossa vertaamme kahta seuraavaa elementtiä, kuten arr[5] ja arr[60].
Koska arr[5] < arr[60], vaihtoa ei tapahdu, koska se on jo lajiteltu nousevaan järjestykseen. Nyt taulukosta tulee:
| 4 | 5 | 60 | 9 |
Iteraatio 3
| 4 | 5 | 60 | 9 |
Kuten kolmannessa iteraatiossa, yhdistämme kolmannen ja neljännen elementin, kuten arr[60] ja arr[9].
Nyt näemme, että arr[60] > arr[9], joten vaihto tapahtuu, jolloin taulukko lajittelee nousevaan järjestykseen.
| 4 | 5 | 9 | 60 |
Näin C:ssä toimii lisäyslajittelu, joka lajittelee taulukon elementin helposti nousevaan tai laskevaan järjestykseen.
Lajittele lisäyksen vuokaavio
Seuraavassa on vuokaavio lisäyslajittelun algoritmista:
Toteutusesimerkki lisäyslajittelusta C:ssä
Tarvitsemme ensin kokoelman elementtejä, jotka on lajiteltava laskevaan ja nousevaan järjestykseen lisätäksemme C:n lisäyslajittelumenetelmän. Oletetaan tässä esimerkissä, että kyseessä on joukko numeroita {5, 4, 60, 9} :
#includemitätön insertionsort_nouseva ( int arr1 [ ] , int n ) {
int i , j , avaimeni ;
//for-silmukkaa käytetään i-arvojen iterointiin välillä 1 - i
varten ( i = 1 ; i < n ; i ++ ) {
avaimeni = arr1 [ i ] ;
j = i - 1 ;
sillä aikaa ( j >= 0 && arr1 [ j ] > avaimeni ) {
arr1 [ j + 1 ] = arr1 [ j ] ;
j = j - 1 ;
}
arr1 [ j + 1 ] = avaimeni ;
}
}
mitätön insertionsort_descending ( int arr2 [ ] , int m ) {
int i , j , avaimeni ;
//toinen for-silmukka luodaan iteroimaan i-arvot välillä 1 - i
varten ( i = 1 ; i < m ; i ++ ) {
avaimeni = arr2 [ i ] ;
j = i - 1 ;
sillä aikaa ( j >= 0 && arr2 [ j ] < avaimeni ) {
arr2 [ j + 1 ] = arr2 [ j ] ;
j = j - 1 ;
}
arr2 [ j + 1 ] = avaimeni ;
}
}
int pää ( ) {
//Insertion-Lajittele laskevassa järjestyksessä
int my_arr [ ] = { 5 , 4 , 60 , 9 } ; //alustaa my_arr[], jolla on neljä arvoa
int m = koko ( my_arr ) / koko ( my_arr [ 0 ] ) ;
insertionsort_descending ( my_arr , m ) ;
printf ( 'Lajiteltu matriisi laskevaan järjestykseen:' ) ;
varten ( int i = 0 ; i < m ; i ++ )
printf ( '%d' , my_arr [ i ] ) ;
printf ( ' \n ' ) ;
//Insertion-Lajittele nousevassa järjestyksessä
int n = koko ( my_arr ) / koko ( my_arr [ 0 ] ) ;
insertionsort_nouseva ( arr2 , n ) ;
printf ( 'Lajiteltu matriisi nousevaan järjestykseen:' ) ;
varten ( int i = 0 ; i < n ; i ++ )
printf ( '%d' , my_arr [ i ] ) ;
printf ( ' \n ' ) ;
palata 0 ;
}
Tässä koodissa kaksi tapaa insertionssort_descending() , ja insertionssort_ascending() ota taulukon arvot my_arr[] . Koodi käyttää sitten a silmukalle iteroidaksesi taulukon elementtien läpi.
Kutsumme molempia funktioita pääfunktiossa, kun ne ovat lajitellut taulukot laskevaan ja nousevaan järjestykseen. Tämän jälkeen for-silmukoilla tulostetaan lajiteltu taulukko.
Kun suoritamme tämän ohjelman, odotettu tulos sijoitetaan alle:
Johtopäätös
Lisäyslajittelu on nopea ja helppo tapa lajitella taulukko joko laskevassa tai nousevassa järjestyksessä. Pienille tietojoukoille tämä lajittelutekniikka toimii hyvin. Kuten yllä olevasta oppaasta näet, on helppo toteuttaa esimerkki C-ohjelmasta, jotta voidaan helposti ymmärtää lisäyslajittelu sekä laskevassa että nousevassa järjestyksessä.