logo

TechCodeview

Sorteringsalgoritmer

A Sorteringsalgoritm används för att ordna om en given array eller lista med element enligt en jämförelseoperator på elementen. Jämförelseoperatorn används för att bestämma den nya ordningen av element i respektive datastruktur.

Till exempel: Listan nedan med tecken sorteras i ökande ordning efter deras ASCII-värden. Det vill säga, tecknet med ett lägre ASCII-värde kommer att placeras först än tecknet med ett högre ASCII-värde.



Innehållsförteckning

Vad är sortering?

Sortering hänvisar till omarrangemang av en given array eller lista av element enligt en jämförelseoperator på elementen. Jämförelseoperatorn används för att bestämma den nya ordningen av element i respektive datastruktur. Sortering innebär omordning av alla element antingen i stigande eller fallande ordning.

Sorteringsterminologi:

  • Sortering på plats: En på plats sorteringsalgoritm använder konstant utrymme för att producera utdata (ändrar endast den givna arrayen). Den sorterar listan endast genom att ändra ordningen på elementen i listan. Exempel: Urvalssortering, Bubbelsorteringsinsättningssortering och Högsortering.
  • Intern sortering: Intern sortering är när all data placeras i huvudminne eller internminne . Vid intern sortering kan problemet inte ta input utöver sin storlek. Exempel: högsortering, bubbelsortering, urvalssortering, snabbsortering, skalsortering, infogningssortering.
  • Extern sortering: Extern sortering är när all data som behöver sorteras inte kan placeras i minnet åt gången, sorteringen kallas för extern sortering. Extern sortering används för den enorma mängden data. Exempel: Slå samman sortering, Tag sortering, Flerfas sortering, Fyra band sortering, Extern radix sortering, etc.
  • Stabil sortering: När två samma data visas i samma beställa i sorterade data utan att ändra deras position kallas stabil sortering. Exempel: Slå samman sortering, infogningssortering, bubbelsortering.
  • Instabil sortering: När två samma data visas i annorlunda beställa i sorterad data kallas det instabil sortering. Exempel: Snabbsortering, Högsortering, Skalsortering .

Egenskaper för sorteringsalgoritmer:

  • Tidskomplexitet: Tidskomplexitet, ett mått på hur lång tid det tar att köra en algoritm, används för att kategorisera sorteringsalgoritmer. Det värsta fallet, det genomsnittliga fallet och det bästa fallet för en sorteringsalgoritm kan användas för att kvantifiera processens tidskomplexitet.
  • Utrymmes komplexitet: Sorteringsalgoritmer har också utrymmeskomplexitet, vilket är mängden minne som krävs för att exekvera algoritmen.
  • Stabilitet: En sorteringsalgoritm sägs vara stabil om den relativa ordningen av lika element bevaras efter sortering. Detta är viktigt i vissa tillämpningar där den ursprungliga ordningen av lika delar måste bibehållas.
  • Sortering på plats: En sorteringsalgoritm på plats är en som inte kräver ytterligare minne för att sortera data. Detta är viktigt när det tillgängliga minnet är begränsat eller när data inte kan flyttas.
  • Anpassningsförmåga: En adaptiv sorteringsalgoritm är en som drar fördel av befintlig ordning i data för att förbättra prestandan.

Tillämpningar av sorteringsalgoritmer:

  • Sökalgoritmer: Sortering är ofta ett avgörande steg i sökalgoritmer som binär sökning, ternär sökning, där data måste sorteras innan man söker efter ett specifikt element.
  • Datahantering: Att sortera data gör det lättare att söka, hämta och analysera.
  • Databasoptimering: Sortering av data i databaser förbättrar frågeprestanda.
  • Maskininlärning: Sortering används för att förbereda data för träning av maskininlärningsmodeller.
  • Dataanalys: Sortering hjälper till att identifiera mönster, trender och extremvärden i datamängder. Den spelar en viktig roll i statistisk analys, finansiell modellering och andra datadrivna områden.
  • Operativsystem: Sorteringsalgoritmer används i operativsystem för uppgifter som uppgiftsschemaläggning, minneshantering och filsystemsorganisation.

Grunderna för sorteringsalgoritmer:

  • Introduktion till sorteringstekniker – handledningar om datastruktur och algoritmer
  • Tillämpningar, fördelar och nackdelar med sorteringsalgoritm
  • Vad är ett verkligt exempel på sortering?
  • Vad är sortering i DSA | Sorterande betydelse

Sorteringsalgoritmer:

Biblioteksimplementeringar:

Enkla problem vid sortering:

  • Sortera element efter frekvens
  • Sortera en matris med 0:or, 1:or och 2:or
  • Sortera nummer lagrade på olika maskiner
  • Sortera en array i vågform
  • Kontrollera om två intervall överlappar en given uppsättning intervall
  • Hur sorterar man en rad datum i C/C++?
  • Sortera strängar med Bubble Sort
  • Hitta saknade element i ett intervall
  • Sortera en array enligt antalet inställda bitar
  • Sortera jämnt placerade element i ökande och udda placerade i minskande ordning
  • Sortera en array när två halvor är sorterade
  • Sortera stora heltal
  • Sortera en länkad lista med 0:or, 1:or och 2:or

Medelstora problem med sortering:

  • Inversionsräkning i Array med Merge Sort
  • Hitta minsta längd osorterad subarray, sortering som gör hela arrayen sorterad
  • Sortera en nästan sorterad (eller K-sorterad) array
  • Sortera n tal i intervallet från 0 till n^2 – 1 i linjär tid
  • Sortera en array enligt den ordning som definieras av en annan array
  • Hitta den punkt där maximala intervall överlappar varandra
  • Hitta en permutation som orsakar det värsta fallet av Merge Sort
  • Sortera vektor av par i stigande ordning i C++
  • Minsta byten för att göra två arrayer identiska
  • Chokladdistributionsproblem
  • Permutera två arrayer så att summan av varje par är större eller lika med K
  • Hinksortering För att sortera en matris med negativa tal
  • Sortera en matris i allt större ordning
  • Konvertera en array till reducerad form med vektor av par
  • Minsta skillnadstriplett från tre arrayer
  • Kontrollera om det är möjligt att sortera en array med villkorligt byte av angränsande tillåtet

Svåra problem med sortering:

  • Hitta Surpasser Count för varje element i arrayen
  • Räkna distinkta händelser som en följd
  • Räkna minsta antal delmängder (eller delsekvenser) med på varandra följande siffror
  • Välj k matriselement så att skillnaden mellan maximum och minimum minimeras
  • Minsta swap krävs för att konvertera binärt träd till binärt sökträd
  • K-te minsta elementet efter att ha tagit bort några heltal från naturliga tal
  • Maximal skillnad mellan frekvensen för två element så att element med högre frekvens också är större
  • Minsta byten för att nå permuterad array med högst 2 positioner vänsterbyten tillåtna
  • Ta reda på om det är möjligt att göra arrayelement lika med ett externt nummer
  • Sortera en matris efter att ha tillämpat den givna ekvationen
  • Skriv ut en rad strängar i sorterad ordning utan att kopiera en sträng till en annan

Snabblänkar :

  • 'Övningsproblem' på sortering
  • 'Frågesporter' om sortering

Rekommenderad:

  • Lär dig datastruktur och algoritmer | Handledning för DSA