Vegye figyelembe a következő számokat:
50 60 30 10 80 70 20 40
Ha ez a lista növekvő sorrendben van rendezve, akkor a következő lenne:
10 20 30 40 50 60 70 80
Ha csökkenő sorrendbe van rendezve, akkor ez lenne:
80 70 60 50 40 30 20 10
A beszúrásos rendezés egy rendezési algoritmus, amely a lista növekvő vagy csökkenő sorrendbe rendezésére szolgál. Ez a cikk csak a növekvő sorrendben történő rendezésről szól. A csökkenő sorrendben történő rendezés a jelen dokumentumban megadott logikát követi. Ennek a cikknek a célja, hogy elmagyarázza a beillesztési rendezést. A programozás a következő példában történik C nyelven. A beillesztési rendezést itt egy tömb használatával magyarázzuk el.
Algoritmus beszúrás rendezéshez
Egy rendezetlen lista látható. A cél az, hogy ugyanazt a listát használva növekvő sorrendbe rendezzük a listát. A rendezetlen tömb ugyanazon tömb használatával történő rendezése helyben történő rendezésnek mondható. Itt a nulla alapú indexelést használjuk. A lépések a következők:
-
- A lista az elejétől kezdve szkennelve.
- A szkennelés közben az elődjénél kisebb számokat felcseréljük az elődjével.
- Ez a csere addig folytatódik a listán, amíg már nem lehet cserélni.
- Amikor a szkennelés a végére ér, a rendezés befejeződik.
Beszúrás rendezési illusztráció
Az időbonyolultság kezelésekor általában a legrosszabb esetet veszik figyelembe. Az előző lista legrosszabb elrendezése a következő:
80 70 60 50 40 30 20 10
Nyolc elemből áll, amelyek indexei nullától 7-ig terjednek.
A nulla indexnél a pásztázás 80-ra megy. Ez egy mozgás. Ez az egyetlen mozdulat egy művelet. Eddig összesen egy művelet van (egy mozgás, nincs összehasonlítás és nincs csere). Az eredmény:
| 80 70 60 50 40 30 20 10
Az első indexnél 70-re van elmozdulás. A 70-et a 80-hoz hasonlítják. 70 és 80 felcserélődik. Egy mozdulat egy művelet. Egy összehasonlítás is egy művelet. Egy csere is egy művelet. Ez a rész három műveletet tartalmaz. Eddig összesen négy művelet van (1 + 3 = 4). Az eredmény a következő:
70 | 80 60 50 40 30 20 10
A második indexnél 60-ra mozdul el. A 60-at összehasonlítja a 80-assal, majd felcseréli a 60-at és a 80-at. A 60-at összehasonlítják a 70-nel, majd felcserélik a 60-at és a 70-et. Egy mozdulat egy művelet. Két összehasonlítás két művelet. Két csere két művelet. Ez a rész öt műveletet tartalmaz. Eddig összesen kilenc művelet van (4 + 5 = 9). Az eredmény a következő:
60 70 | 80 50 40 30 20 10
A harmadik indexnél 50-re mozdul el. Az 50-et összehasonlítják a 80-zal, majd felcserélik az 50-et és a 80-at. Az 50-et összehasonlítják a 70-nel, majd felcserélik az 50-et és a 70-et. Az 50-et összehasonlítják a 60-al, majd felcserélik az 50-et és a 60-at. Egy mozdulat egy művelet. Három összehasonlítás három művelet. Három csere három művelet. Ez a rész hét műveletet tartalmaz. Eddig összesen tizenhat művelet van (9 + 7 = 16). Az eredmény a következő:
50 60 70 | 80 40 30 20 10
A négyes indexnél 40-re van elmozdulás. A 40-et összehasonlítják a 80-zal, majd felcserélik a 40-et és a 80-at. A 40-et összehasonlítják a 70-nel, majd a 40-et és a 70-et felcserélik. A 40-et összehasonlítják a 60-al, majd felcserélik a 40-et és a 60-at. A 40-et összehasonlítják az 50-nel, majd a 40-et és az 50-et felcserélik. Egy mozdulat egy művelet. Négy összehasonlítás négy művelet. Négy swap négy művelet. Ez a rész kilenc műveletet tartalmaz. Eddig összesen huszonöt művelet van (16 + 9 = 25). Az eredmény a következő:
40 50 60 70 80 | 30 20 10
Az ötös indexnél 30-ra mozdul el. A 30-at összehasonlítják a 80-assal, majd felcserélik a 30-at és a 80-at. A 30-at összehasonlítják a 70-nel, majd felcserélik a 30-at és a 70-et. A 30-at összehasonlítják a 60-al, majd felcserélik a 30-at és a 60-at. A 30-at összehasonlítják az 50-nel, majd felcserélik a 30-at és az 50-et. A 30-at összehasonlítják a 40-el, majd felcserélik a 30-at és a 40-et. Egy mozdulat egy művelet. Öt összehasonlítás öt művelet. Öt swap öt művelet. Ez a rész tizenegy műveletet tartalmaz. Eddig összesen harminchat művelet van (25 + 11 = 36). Az eredmény a következő:
30 40 50 60 70 80 | 20 10
A hatodik indexnél 20-ra mozdul el. A 20-at összehasonlítják a 80-zal, majd felcserélik a 20-at és a 80-at. A 20-at összehasonlítják a 70-nel, majd felcserélik a 20-at és a 70-et. A 20-at összehasonlítják a 60-al, majd felcserélik a 20-at és a 60-at. A 20-at összehasonlítják az 50-nel, majd felcserélik a 20-at és az 50-et. A 20-at összehasonlítjuk a 40-el, majd a 20-at és a 40-et felcseréljük. A 20-at összehasonlítjuk a 30-al, majd a 20-at és a 30-at felcseréljük. Egy mozdulat egy művelet. Hat összehasonlítás hat művelet. Hat csereügylet hat művelet. Ez a rész tizenhárom műveletet tartalmaz. Eddig összesen negyvenkilenc művelet van (36 + 13 = 49). Az eredmény a következő:
20 30 40 50 60 70 80 | 10
A hetedik indexnél 10-re mozdulnak el. A 10-et összehasonlítják a 80-zal, majd felcserélik a 10-et és a 80-at. A 10-et összehasonlítja a 70-nel, majd felcseréli a 10-et és a 70-et. A 10-et összehasonlítja a 60-al, majd felcseréli a 10-et és a 60-at. A 10-et összehasonlítja az 50-nel, majd felcseréli a 10-et és az 50-et. A 10-et összehasonlítja a 30-zal, majd felcseréli a 10-et és a 40-et. A 10-et összehasonlítja a 30-zal, majd felcseréli a 10-et és a 30-at. A 10-et összehasonlítjuk a 20-zal, majd a 10-et és a 20-at felcseréljük. Egy mozdulat egy művelet. Hét összehasonlítás hét művelet. Hét csereügylet hét művelet. Ez a rész tizenöt műveletet tartalmaz. Eddig összesen hatvannégy művelet van (49 + 15 = 64). Az eredmény a következő:
10 20 30 40 50 60 70 80 10 |
A munka kész! 64 műveletről volt szó.
64 = 8 x 8 = 8 két
Időbeli összetettség a beillesztési rendezéshez
Ha n elemet kell rendezni az Insertion Sort funkcióval, akkor a lehetséges műveletek maximális száma n2 lesz, amint azt korábban bemutattuk. A beillesztési rendezési idő bonyolultsága a következő:
Tovább két )
Ez a Big-O jelölést használja. A Big-O jelölés nagybetűs O-val kezdődik, amelyet zárójel követ. A zárójelben található a műveletek maximális számának kifejezése.
Kódolás C-ben
A vizsgálat legelején az első elem nem tudja megváltoztatni a helyzetét. A program lényegében a következő:
#includeüres beillesztés Rendezés ( int A [ ] , int N ) {
számára ( int én = 0 ; én < N; i++ ) {
int j = i;
míg ( A [ j ] < A [ j- 1 ] && j- 1 > = 0 ) {
belső hőmérséklet = A [ j ] ; A [ j ] = A [ j- 1 ] ; A [ j- 1 ] = hőmérséklet; // csere
j--;
}
}
}
Az insertionSort() függvénydefiníció a leírt algoritmust használja. Vegye figyelembe a while ciklus feltételeit. A program megfelelő C fő funkciója:
{
int n = 8 ;
int A [ ] = { ötven , 60 , 30 , 10 , 80 , 70 , húsz , 40 } ;
beszúrásSort ( A, n ) ;
számára ( int én = 0 ; én < n; i++ ) {
printf ( '%i' , A [ én ] ) ;
}
printf ( ' \n ' ) ;
Visszatérés 0 ;
}
Következtetés
A beillesztési rendezés időbeli összetettsége a következő:
Tovább két )
Az olvasó talán hallott a rosszabb esetek bonyolultságáról, az átlagos esetek bonyolultságáról és a legjobb eset összetettségéről. A beszúrási rendezési idő összetettségének ezen változatait a weboldalunk következő cikkében tárgyaljuk.