Što je sortiranje umetanjem u C?
Metoda razvrstavanja koja se naziva sortiranje umetanjem povezuje svaki pojedinačni element sa susjednim elementima dok ponavlja kroz niz. Manji element od onog prije njega umetnut je u sortiranu podnizu na odgovarajuće mjesto.
Za daljnju ilustraciju, demonstrirao sam primjer u kojem sam razmatrao niz od četiri elementa u nizu kao što je arr[]= {5, 4, 60, 9} i želimo sortirati ovaj element uzlaznim redoslijedom pomoću sortiranja umetanjem. Sljedeće interakcije objašnjavaju potpunu prohujalu sortiranja umetanja:
Iteracija 1
| 5 | 4 | 60 | 9 |
Sada imamo niz kao arr[5, 4, 60, 9], u prvoj iteraciji sortiranja umetanjem prvo uspoređujemo prva dva elementa kao što su 5 i 4, budući da je arr[5] > arr[4] pa mijenjamo ih kako bismo poredali niz uzlaznim redoslijedom. Sada će niz biti:
| 4 | 5 | 60 | 9 |
Ponavljanje 2
| 4 | 5 | 60 | 9 |
U drugoj iteraciji uspoređujemo sljedeća dva elementa, kao što je arr[5] s arr[60].
Budući da je arr[5] < arr[60], zamjena se ne događa jer je već sortirano uzlaznim redoslijedom. Sada niz postaje:
| 4 | 5 | 60 | 9 |
Ponavljanje 3
| 4 | 5 | 60 | 9 |
Kao u trećoj iteraciji, povezujemo treći i četvrti element kao arr[60] s arr[9].
Sada vidimo da arr[60] > arr[9] pa dolazi do zamjene, tada će niz sortirati uzlaznim redoslijedom.
| 4 | 5 | 9 | 60 |
Ovako funkcionira sortiranje umetanjem u C-u koji lako razvrstava elemente niza uzlaznim ili silaznim redoslijedom.
Dijagram toka sortiranja umetanjem
Slijedi dijagram toka algoritma sortiranja umetanjem:
Primjer implementacije sortiranja umetanjem u C
Prvo nam je potrebna kolekcija elemenata koje je potrebno poredati silaznim i uzlaznim redoslijedom kako bismo izgradili metodu sortiranja umetanjem u C. Pretpostavimo za potrebe ovog primjera da imamo posla s nizom brojeva {5, 4, 60, 9} :
#includeponištiti umetanja sortiranje_uzlazno ( int arr1 [ ] , int n ) {
int ja , j , moj_ključ ;
//for petlja se koristi za ponavljanje i vrijednosti od 1 do i
za ( ja = 1 ; ja < n ; ja ++ ) {
moj_ključ = arr1 [ ja ] ;
j = ja - 1 ;
dok ( j >= 0 && arr1 [ j ] > moj_ključ ) {
arr1 [ j + 1 ] = arr1 [ j ] ;
j = j - 1 ;
}
arr1 [ j + 1 ] = moj_ključ ;
}
}
poništiti umetanja sortiranje_silazno ( int arr2 [ ] , int m ) {
int ja , j , moj_ključ ;
//stvorena je još jedna for petlja za ponavljanje i vrijednosti od 1 do i
za ( ja = 1 ; ja < m ; ja ++ ) {
moj_ključ = arr2 [ ja ] ;
j = ja - 1 ;
dok ( j >= 0 && arr2 [ j ] < moj_ključ ) {
arr2 [ j + 1 ] = arr2 [ j ] ;
j = j - 1 ;
}
arr2 [ j + 1 ] = moj_ključ ;
}
}
int glavni ( ) {
//Umetanje-Sortiraj silaznim redoslijedom
int moj_arr [ ] = { 5 , 4 , 60 , 9 } ; //inicijalizirati my_arr[] koji ima četiri vrijednosti
int m = veličina ( moj_arr ) / veličina ( moj_arr [ 0 ] ) ;
umetanja sortiranje_silazno ( moj_arr , m ) ;
printf ( 'Sortirano polje silaznim redoslijedom: ' ) ;
za ( int ja = 0 ; ja < m ; ja ++ )
printf ( '%d' , moj_arr [ ja ] ) ;
printf ( ' \n ' ) ;
//Umetanje-Sortiraj uzlaznim redoslijedom
int n = veličina ( moj_arr ) / veličina ( moj_arr [ 0 ] ) ;
umetanja sortiranje_uzlazno ( arr2 , n ) ;
printf ( 'Sortirano polje uzlaznim redoslijedom: ' ) ;
za ( int ja = 0 ; ja < n ; ja ++ )
printf ( '%d' , moj_arr [ ja ] ) ;
printf ( ' \n ' ) ;
povratak 0 ;
}
U ovom kodu, dvije metode umetanje sortiranje_padajuće() , i sortiranje_umetanja uzlazno() uzeti vrijednosti niza moj_arr[] . Kod tada koristi a za petlju iterirati kroz elemente niza.
Pozivamo obje funkcije u glavnoj funkciji nakon što su poredale nizove u silaznom i uzlaznom redoslijedu. Nakon toga, for petlje se koriste za ispis sortiranog niza.
Kada pokrenemo ovaj program, očekivani rezultat nalazi se ispod:
Zaključak
Sortiranje umetanjem brz je i jednostavan način sortiranja niza u silaznom ili uzlaznom nizu. Za male skupove podataka ova tehnika sortiranja dobro funkcionira. Kao što možete vidjeti u gornjem vodiču, jednostavno je implementirati primjer C programa za jednostavno razumijevanje sortiranja umetanjem u silaznom i uzlaznom redoslijedu.