Sortering är en av de mest grundläggande och användbara funktionerna som tillämpas på data. Det syftar till att ordna data på ett visst sätt, vilket kan öka eller minska enligt kraven. Det finns en inbyggd funktion i C ++ STL med namnet 'sort ()' som gör att vi enkelt kan utföra sorteringsalgoritmer. I den här artikeln kommer vi att utforska sorteringsfunktionen i C ++,
Följande tips kommer att behandlas i den här artikeln:
- Sortera () funktion
- Exempel - Att sortera data i stigande ordning
- Exempel - För att sortera data i fallande ordning
- Partial_sort
Fortsätter med den här artikeln om sorteringsfunktion i C ++
Sortera ( ) -funktion
Det är en inbyggd funktion av algoritmhuvudfilen den används för att sortera behållarna som en matris, vektorer i en angiven ordning. Internt är denna funktion implementerad som Quick-sort
Quicksort är en splittrings- och erövringsalgoritm. Quicksort delar först en stor lista med element i två mindre underlistor: de lägre elementen och de högre elementen. Quicksort sorterar sedan underlistorna rekursivt.
Stegen är som följer:
1. Välj ett slumpmässigt element (vanligtvis det sista elementet), kallat pivot, från listan.
2. Ordna om listan på ett sådant sätt att alla element med värden mindre än pivoten kommer före pivoten, medan alla element med värden som är större än pivoten kommer efter den och lika värden kan gå åt båda hållen, detta kallas process.
3. Sortera underlistan med mindre element och underlistan med större element rekursivt, välj igen en pivot i underlistan och dela dem.
Basfallet för rekursionen är listor av storlek noll eller en, som aldrig behöver sorteras och därmed sorterar vi vår lista genom att kombinera dem.
Quicksort är snabbare i praktiken än andra O (n log n) algoritmer som Insertion Sort eller Bubble sort. Quicksort kan implementeras med en på plats partitioneringsalgoritm, vilket innebär att hela sorteringen kan göras med endast O (log n) extra utrymme. Quicksort är inte en stabil sort.
Dess komplexitet är som följer:
Bästa fall - O (n log n)
Värsta fall - O (n ^ 2)
Genomsnittligt fall - O (n log n)
Syntax:
sortera (första, sista)
Här,
först - är indexet (pekaren) för det första elementet i området som ska sorteras.
sista - är indexet (pekaren) för det sista elementet i det område som ska sorteras.
Till exempel vill vi sortera element i en array 'arr' från 1 till 10 position, vi kommer att använda sort (arr, arr + 10) och det kommer att sortera 10 element i stigande ordning.
Returvärde
Ingen
Komplexitet
Medelvärdet för en sorteringskomplexitet är N * log2 (N), där N = senast - först.
Dataområde
Objektet i intervallet [första, sista] modifieras.
Undantag
Överbelastningarna med en mallparameter som heter ExecutionPolicy-rapportfel enligt följande:
Om algoritmen inte allokerar minne kastas std :: bad_alloc som ett undantag.
Om körningen av en funktion åberopas som en del av algoritmen, kastar den ett undantag std :: terminate.
def __init__ i python
Fortsätter med den här artikeln om sorteringsfunktion i C ++
Exempel - För att sortera data i stigande ordning:
#include using namespace std int main () {int array [] = {10, 35, 85, 93, 62, 77, 345, 43, 2, 10} int n = sizeof (array) / sizeof (array [0] ) // 'sizeof' ger storleken på den totala matrisen, dvs. storleken på varje tecken * nr. av tecken // så för att få nej. av tecken // vi delar storleken på (array) med storleken på ett tecken i arrayen // här är det array [0] sort (array, array + n) cout<< 'nArray after sorting using ' 'default sort is : n' for (int i = 0 i < n ++i) cout << array[i] << ' ' return 0 } Utgång:
Förklaring
Från exemplet ovan ser vi att sorteringsfunktionen () som standard sorterar en matris i stigande ordning.
Fortsätter med den här artikeln om sorteringsfunktion i C ++
abstrakt klass och gränssnittsskillnad
Exempel - För att sortera data i fallande ordning:
För att sortera data i matrisen i fallande ordning måste vi införa en tredje parameter som används för att ange ordningen i vilken element ska sorteras. Vi kan använda funktionen “större ()” för att sortera data i fallande ordning.
#include using namespace std int main () {int array [] = {41, 53, 4, 459, 60, 7, 23, 4, 232, 10} int n = sizeof (array) / sizeof (array [0] ) sortera (array, array + n, större ()) cout<< 'Array after sorting : n' for (int i = 0 i < n ++i) cout << array[i] << ' ' return 0 } Produktion:
Exp l en nation
Här gör sort () -funktionen en jämförelse på ett sätt som sätter större element före.
Fortsätter med den här artikeln om sorteringsfunktion i C ++
Partial_sort
C ++ STL ger oss en partiell sorteringsfunktion, funktionen liknar sorteringsfunktionen () men till skillnad från sorteringsfunktionen () används den inte för att sortera hela intervallet utan den används bara för att sortera en del av den. Det sorterar elementen i intervallet [första, sista) på ett sådant sätt att elementen före mittelementet sorteras i stigande ordning, medan elementen efter mitten lämnas som det är.
Det kan användas för att hitta det största elementet om vi använder ett funktionsobjekt för att sortera efter den första positionen
Exempel
#include #include #include med hjälp av namespace std int main () {vector vec = {10, 45, 60, 78, 23, 21, 30} vector :: iterator iptr partial_sort (vec.begin (), vec.begin () + 1, vec.end (), större ()) iptr = vec.begin () cout<< 'The largest element is = ' << *iptr return 0 } Produktion:
Förklaring:
Ovanstående kod kan användas för att hitta det största antalet i en serie, för att hitta det minsta antalet i serien behöver vi bara ta bort det större kommandot.
Således har vi kommit till slutet av den här artikeln om ”Sortera funktion i C ++”. Om du vill lära dig mer, kolla in Java Training av Edureka, ett pålitligt online-lärande företag. Edureka's kursen är utformad för att träna dig för både kärn- och avancerade Java-koncept tillsammans med olika Java-ramverk som Hibernate & Spring.
Har du en fråga till oss? Vänligen nämna det i kommentarsektionen på den här bloggen så kommer vi tillbaka till dig så snart som möjligt.