Razmotrite sljedeće brojeve:
50 60 30 10 80 70 20 40
Ako je ovaj popis poredan uzlaznim redoslijedom, to bi bilo:
10 20 30 40 50 60 70 80
Ako je poredano silaznim redoslijedom, to bi bilo:
80 70 60 50 40 30 20 10
Sortiranje umetanjem algoritam je za sortiranje koji se koristi za sortiranje popisa uzlaznim ili silaznim redoslijedom. Ovaj se članak bavi samo sortiranjem uzlaznim redoslijedom. Razvrstavanje silaznim redoslijedom slijedi istu logiku danu u ovom dokumentu. Cilj ovog članka je objasniti vrstu umetanja. Programiranje se vrši u sljedećem primjeru u C-u. Ovdje je objašnjeno sortiranje umetanjem koristeći jedno polje.
Algoritam za sortiranje umetanjem
Dat je nesortirani popis. Cilj je poredati popis uzlaznim redoslijedom koristeći isti popis. Sortiranje nesortiranog niza pomoću istog niza naziva se sortiranjem na mjestu. Ovdje se koristi indeksiranje temeljeno na nuli. Koraci su sljedeći:
-
- Popis se skenira od početka.
- Dok skeniranje traje, svaki broj manji od svog prethodnika zamjenjuje se sa svojim prethodnikom.
- Ova zamjena se nastavlja duž liste, sve dok zamjena više nije moguća.
- Kada skeniranje dođe do kraja, sortiranje je završeno.
Ilustracija sortiranja umetanjem
Kada se radi o vremenskoj složenosti, to je najgori slučaj koji se obično uzima u obzir. Najgori raspored za prethodni popis je:
80 70 60 50 40 30 20 10
Postoji osam elemenata s indeksima od nula do 7.
Na indeksu nula, skeniranje ide na 80. Ovo je jedan pokret. Ovaj jedan pokret je operacija. Do sada postoji ukupno jedna operacija (jedno kretanje, bez usporedbe i bez zamjene). Rezultat je:
| 80 70 60 50 40 30 20 10
Kod indeksa jedan dolazi do pomaka na 70. 70 se uspoređuje s 80. 70 i 80 se zamjenjuju. Jedan pokret je jedna operacija. Jedna usporedba je također jedna operacija. Jedna zamjena također je jedna operacija. Ovaj odjeljak nudi tri operacije. Do sada su ukupno četiri operacije (1 + 3 = 4). Rezultat je sljedeći:
70 | 80 60 50 40 30 20 10
Kod indeksa dva dolazi do pomaka na 60. 60 se uspoređuje s 80, zatim se 60 i 80 zamjenjuju. 60 se uspoređuje sa 70, zatim se 60 i 70 zamjenjuju. Jedan pokret je jedna operacija. Dvije usporedbe su dvije operacije. Dvije zamjene su dvije operacije. Ovaj dio nudi pet operacija. Do sada je ukupno devet operacija (4 + 5 = 9). Rezultat je sljedeći:
60 70 | 80 50 40 30 20 10
Kod indeksa tri dolazi do pomaka na 50. 50 se uspoređuje s 80, zatim se 50 i 80 zamjenjuju. 50 se uspoređuje sa 70, zatim se 50 i 70 zamjenjuju. 50 se uspoređuje sa 60, zatim se 50 i 60 zamjenjuju. Jedan pokret je jedna operacija. Tri usporedbe su tri operacije. Tri zamjene su tri operacije. Ovaj dio nudi sedam operacija. Do sada je ukupno šesnaest operacija (9 + 7 = 16). Rezultat je sljedeći:
50 60 70 | 80 40 30 20 10
Kod indeksa četiri dolazi do pomaka na 40. 40 se uspoređuje s 80, zatim se 40 i 80 zamjenjuju. 40 se uspoređuje sa 70, zatim se 40 i 70 zamjenjuju. 40 se uspoređuje sa 60, zatim se 40 i 60 zamjenjuju. 40 se uspoređuje s 50, zatim se 40 i 50 zamjenjuju. Jedan pokret je jedna operacija. Četiri usporedbe su četiri operacije. Četiri zamjene su četiri operacije. Ovaj dio nudi devet operacija. Do sada je ukupno dvadeset i pet operacija (16 + 9 = 25). Rezultat je sljedeći:
40 50 60 70 80 | 30 20 10
Kod indeksa pet dolazi do pomaka na 30. 30 se uspoređuje s 80, zatim se 30 i 80 zamjenjuju. 30 se uspoređuje sa 70, zatim se 30 i 70 zamjenjuju. 30 se uspoređuje sa 60, zatim se 30 i 60 zamjenjuju. 30 se uspoređuje s 50, zatim se 30 i 50 zamjenjuju. 30 se uspoređuje s 40, zatim se 30 i 40 zamjenjuju. Jedan pokret je jedna operacija. Pet usporedbi je pet operacija. Pet zamjena je pet operacija. Ovaj dio nudi jedanaest operacija. Do sada je ukupno trideset i šest operacija (25 + 11 = 36). Rezultat je sljedeći:
30 40 50 60 70 80 | 20 10
Kod indeksa šest dolazi do pomaka na 20. 20 se uspoređuje s 80, zatim se 20 i 80 zamjenjuju. 20 se uspoređuje sa 70, zatim se 20 i 70 zamjenjuju. 20 se uspoređuje sa 60, zatim se 20 i 60 zamjenjuju. 20 se uspoređuje s 50, zatim se 20 i 50 zamjenjuju. 20 se uspoređuje s 40, zatim se 20 i 40 zamjenjuju. 20 se uspoređuje s 30, zatim se 20 i 30 zamjenjuju. Jedan pokret je jedna operacija. Šest usporedbi je šest operacija. Šest zamjena je šest operacija. Ovaj dio nudi trinaest operacija. Do sada je ukupno četrdeset i devet operacija (36 + 13 = 49). Rezultat je sljedeći:
20 30 40 50 60 70 80 | 10
Kod indeksa sedam dolazi do pomaka na 10. 10 se uspoređuje s 80, zatim se 10 i 80 zamjenjuju. 10 se uspoređuje sa 70, zatim se 10 i 70 zamjenjuju. 10 se uspoređuje sa 60, zatim se 10 i 60 mijenjaju. 10 se uspoređuje s 50, zatim se 10 i 50 zamjenjuju. 10 se uspoređuje s 30, zatim se 10 i 40 zamjenjuju. 10 se uspoređuje s 30, zatim se 10 i 30 zamjenjuju. 10 se uspoređuje s 20, zatim se 10 i 20 zamjenjuju. Jedan pokret je jedna operacija. Sedam usporedbi je sedam operacija. Sedam zamjena je sedam operacija. Ovaj dio nudi petnaest operacija. Do sada su ukupno šezdeset i četiri operacije (49 + 15 = 64). Rezultat je sljedeći:
10 20 30 40 50 60 70 80 10 |
Posao je gotov! Uključene su 64 operacije.
64 = 8 x 8 = 8 dva
Vremenska složenost za sortiranje umetanjem
Ako postoji n elemenata za sortiranje pomoću Sortiranja umetanjem, najveći broj mogućih operacija bio bi n2, kao što je prethodno pokazano. Složenost vremena sortiranja umetanja je:
Na dva )
Ovdje se koristi oznaka Big-O. Oznaka Big-O počinje s O velikim slovima, nakon čega slijede zagrade. Unutar zagrada nalazi se izraz za najveći mogući broj operacija.
Kodiranje u C
Na samom početku skeniranja prvi element ne može promijeniti svoju poziciju. Program je u biti sljedeći:
#includevoid insertionSort ( int A [ ] , int N ) {
za ( int ja = 0 ; ja < N; i++ ) {
int j = i;
dok ( A [ j ] < A [ j- 1 ] && j- 1 > = 0 ) {
int temp = A [ j ] ; A [ j ] = A [ j- 1 ] ; A [ j- 1 ] = temp; // zamijeniti
j--;
}
}
}
Definicija funkcije insertionSort() koristi algoritam kako je opisano. Zabilježite uvjete za while-petlju. Prikladna C glavna funkcija za ovaj program je:
{
int n = 8 ;
int A [ ] = { pedeset , 60 , 30 , 10 , 80 , 70 , dvadeset , 40 } ;
umetanjeSortiraj ( A, n ) ;
za ( int ja = 0 ; ja < n; i++ ) {
printf ( '%i' , A [ ja ] ) ;
}
printf ( ' \n ' ) ;
povratak 0 ;
}
Zaključak
Vremenska složenost za sortiranje umetanjem dana je kao:
Na dva )
Čitatelj je možda čuo za vremensku složenost u gorem slučaju, prosječnu vremensku složenost i najbolju vremensku složenost. O ovim varijacijama vremenske složenosti sortiranja umetanjem raspravlja se u sljedećem članku na našoj web stranici.