Sortering är en grundläggande operation där elementen i en array är ordnade i en viss specifik ordning för att förbättra sökbarheten. I enkla ord sorteras data så att det enkelt kan sökas.
Jämförelsediagram
| Grunder för jämförelse | Insertion Sortera | Urval Sortera |
|---|---|---|
| Grundläggande | Uppgifterna sorteras genom att infoga data i en befintlig sorterad fil. | Uppgifterna sorteras genom att välja och placera de på varandra följande elementen i sorterad plats. |
| Natur | Stabil | Instabil |
| Process som ska följas | Element är kända på förhand medan plats för att placera dem sökes. | Plats är tidigare känt medan element söks. |
| Omedelbar data | Insertion sort är live sortering teknik som kan hantera omedelbara data. | Det kan inte hantera omedelbara data, det måste vara närvarande i början. |
| Bästa fallskomplexitet | På) | O (n2) |
Definition av Insertion Sort
Infognings sorter fungerar genom att infoga värdena i den befintliga sorterade filen. Den konstruerar den sorterade arrayen genom att infoga ett enda element i taget. Denna process fortsätter tills hela arrayen sorteras i viss ordning. Det primära konceptet bakom inmatningssort är att infoga varje objekt på lämpligt ställe i slutlistan. Inmatnings sorteringsmetoden sparar en effektiv mängd minne.
Arbeta med Insertion-sorten
- Den använder två uppsättningar av arrayer där man lagrar de sorterade data och andra på osorterade data.
- Sorteringsalgoritmen fungerar tills det finns element i den osorterade uppsättningen.
- Låt oss anta att det finns 'n' talelement i matrisen. Ursprungligen finns elementet med index 0 (LB = 0) i den sorterade uppsättningen. Återstående element finns i den osorterade partitionen i listan.
- Det första elementet i den osorterade delen har arrayindex 1 (om LB = 0).
- Efter varje iteration väljer den det första elementet i den osorterade partitionen och sätter den in på rätt plats i den sorterade uppsättningen.
Fördelar med Insertion sort
- Lätt implementerad och mycket effektiv när den används med små uppsättningar data.
- Det extra minnesutrymmet för insättningssort är mindre (dvs O (1)).
- Det anses vara levande sorteringsteknik eftersom listan kan sorteras efter att de nya elementen har tagits emot.
- Det är snabbare än andra sorteringsalgoritmer.
Exempel:
Definition av urvalssortering
Sorteringsvalet utför sortering genom att söka efter minimivärdet och placera det i första eller sista positionen enligt ordningen (stigande eller nedåtgående). Processen att söka minsta nyckeln och placera den i rätt position fortsätter tills alla elementen är placerade i rätt position.
Arbeta med urvalssorteringen
- Antag en array ARR med N element i minnet.
- I det första passet söks den minsta nyckeln tillsammans med sin position då ARR [POS] byts ut med ARR [0]. Därför sorteras ARR [0].
- I det andra passet bestäms återigen läget för det minsta värdet i subarrayen av N-1-element. Byt ARR [POS] med ARR [1].
- I passet N-1 utförs samma process för att sortera N-talet av element.
Exempel:
Viktiga skillnader mellan sortering och sortering av sortering
- Inläggssortet utför vanligtvis inläggsoperationen. Tvärtom utför sortvalet urvalet och positioneringen av de erforderliga elementen.
- Inmatningssortet sägs vara stabilt, medan urvalstyp inte är en stabil algoritm.
- I inmatningssortalgoritmen är elementen tidigare kända. I kontrast innehåller sorteringsorten platsen i förväg.
- Insertion sort är en live sorteringsteknik där de anlända elementen sorteras omedelbart i listan medan sorterings sorten inte fungerar bra med omedelbara data.
- Inläggssortet har O (n) speltid i bästa fall. Däremot är det bästa fallet att komplexiteten i valet sorteras är O (n2).
Komplexiteten i Insertion-sorten
Den bästa fallskomplexiteten för införingssorteringen är O (n) gånger, dvs när arrayen tidigare sorterats. På samma sätt, när arrayen sorteras i omvänd ordning, ska det första elementet i den osorterade gruppen jämföras med varje element i den sorterade uppsättningen. Så, i värsta fall är körtiden för Insertion-sorten kvadratisk, dvs O (n2) . I genomsnitt måste det också göra minsta (k-1) / 2 jämförelser. Därför har det genomsnittliga fallet också kvadratisk körtid O (n2).
Komplexiteten i urvalssorten
Sortering av sortering beror inte på den ursprungliga ordningen av elementen i matrisen, så det finns ingen stor skillnad mellan bästa fallet och det sämsta fallet av komplexiteten i sortimentet.
Valet sorterar väljer minimivärdeelementet, i valprocessen skannas alla n 'antal element; därför görs n-1 jämförelser i första passet. Därefter byts elementen. På samma sätt i det andra passet också för att hitta det näst minsta elementet behöver vi skanning av vila n-1-element och processen fortsätter tills hela sorten sorteras.
Således är körtidskomplexiteten för urvalssorteringen O (n2) .
= (n-1) + (n-2) + ......... .. + 2 + 1
= n (n-1) / 2 = 0 (n2)
Slutsats
Bland sorteringsalgoritmen är inläggssortet snabbt, effektivt och stabilt medan sorterings sorteringen endast fungerar effektivt när den lilla uppsättningen av element är inblandad eller listan sorteras delvis tidigare. Antalet jämförelser som gjorts av sorteringssorteringen är större än de rörelser som utförts, medan i inmatning sorteras antalet gånger ett element flyttas eller bytas är större än jämförelserna.
