logo

TechCodeview

Sorteringsalgoritmer

EN Sorteringsalgoritme bruges til at omarrangere en given matrix eller liste over elementer i henhold til en sammenligningsoperator på elementerne. Sammenligningsoperatoren bruges til at bestemme den nye rækkefølge af elementer i den respektive datastruktur.

For eksempel: Nedenstående liste over tegn er sorteret i stigende rækkefølge efter deres ASCII-værdier. Det vil sige, at tegnet med en lavere ASCII-værdi vil blive placeret først end tegnet med en højere ASCII-værdi.



nusset log

Indholdsfortegnelse

Hvad er sortering?

Sortering refererer til omarrangering af en given matrix eller liste af elementer i henhold til en sammenligningsoperator på elementerne. Sammenligningsoperatoren bruges til at bestemme den nye rækkefølge af elementer i den respektive datastruktur. Sortering betyder omarrangering af alle elementer enten i stigende eller faldende rækkefølge.



konvertere en dato til en streng

Sorteringsterminologi:

  • Sortering på stedet: En in-place sorteringsalgoritme bruger konstant plads til produktion af output (ændrer kun det givne array). Den sorterer kun listen ved at ændre rækkefølgen af ​​elementerne på listen. Eksempler: Udvælgelsessortering, Boblesortering Indsættelsessortering og Dyngesortering.
  • Intern sortering: Intern sortering er, når alle data er placeret i primære hukommelse eller intern hukommelse . Ved intern sortering kan problemet ikke tage input ud over dets størrelse. Eksempel: bunkesortering, boblesortering, udvælgelsessortering, hurtig sortering, skalsortering, indsættelsessortering.
  • Ekstern sortering: Ekstern sortering er, når alle de data, der skal sorteres, ikke kan placeres i hukommelsen ad gangen, sorteringen kaldes ekstern sortering. Ekstern sortering bruges til den enorme mængde data. Eksempler: Merge sortering, Tag sortering, Polyphase sortering, Fire tape sortering, Ekstern radix sortering osv.
  • Stabil sortering: Når to samme data vises i samme bestille i sorterede data uden at ændre deres position kaldes stabil sortering. Eksempler: Merge Sort, Insertion Sort, Boble Sort.
  • Ustabil sortering: Når to samme data vises i forskellige bestille i sorterede data kaldes det ustabil sortering. Eksempler: Hurtig sortering, bunkesortering, skalsortering .

Karakteristika for sorteringsalgoritmer:

  • Tidskompleksitet: Tidskompleksitet, et mål for, hvor lang tid det tager at køre en algoritme, bruges til at kategorisere sorteringsalgoritmer. Worst-case, gennemsnit-case og bedste-case ydeevnen af ​​en sorteringsalgoritme kan bruges til at kvantificere processens tidskompleksitet.
  • Rumkompleksitet: Sorteringsalgoritmer har også pladskompleksitet, som er den mængde hukommelse, der kræves for at udføre algoritmen.
  • Stabilitet: En sorteringsalgoritme siges at være stabil, hvis den relative rækkefølge af lige store elementer bevares efter sortering. Dette er vigtigt i visse applikationer, hvor den oprindelige rækkefølge af lige elementer skal bibeholdes.
  • Sortering på stedet: En in-place sorteringsalgoritme er en, der ikke kræver yderligere hukommelse for at sortere dataene. Dette er vigtigt, når den tilgængelige hukommelse er begrænset, eller når dataene ikke kan flyttes.
  • Tilpasningsevne: En adaptiv sorteringsalgoritme er en, der udnytter den allerede eksisterende rækkefølge i dataene til at forbedre ydeevnen.

Anvendelser af sorteringsalgoritmer:

  • Søgealgoritmer: Sortering er ofte et afgørende trin i søgealgoritmer som binær søgning, ternær søgning, hvor dataene skal sorteres, før der søges efter et specifikt element.
  • Datastyring: Sortering af data gør det nemmere at søge, hente og analysere.
  • Databaseoptimering: Sortering af data i databaser forbedrer forespørgselsydeevne.
  • Maskinelæring: Sortering bruges til at forberede data til træning af maskinlæringsmodeller.
  • Dataanalyse: Sortering hjælper med at identificere mønstre, tendenser og outliers i datasæt. Det spiller en afgørende rolle i statistisk analyse, finansiel modellering og andre datadrevne felter.
  • Operativsystemer: Sorteringsalgoritmer bruges i operativsystemer til opgaver som opgaveplanlægning, hukommelsesstyring og filsystemorganisation.

Grundlæggende om sorteringsalgoritmer:

  • Introduktion til sorteringsteknikker – datastruktur og algoritmevejledninger
  • Anvendelser, fordele og ulemper ved sorteringsalgoritme
  • Hvad er et virkeligt eksempel på sortering?
  • Hvad er sortering i DSA | Sortering af betydning

Sorteringsalgoritmer:

Biblioteksimplementeringer:

Lette problemer med sortering:

  • Sorter elementer efter frekvens
  • Sorter et array af 0'ere, 1'ere og 2'ere
  • Sorter numre gemt på forskellige maskiner
  • Sorter et array i bølgeform
  • Kontroller, om to intervaller overlapper mellem et givet sæt af intervaller
  • Hvordan sorterer man en række datoer i C/C++?
  • Sortering af strenge ved hjælp af Bubble Sort
  • Find manglende elementer i et område
  • Sorter et array efter antallet af sæt bits
  • Sorter lige-placerede elementer i stigende og ulige-placeret i faldende rækkefølge
  • Sorter et array, når to halvdele er sorteret
  • Sortering af store heltal
  • Sorter en sammenkædet liste med 0'ere, 1'ere og 2'ere

Mellemstore problemer med sortering:

  • Inversionstal i Array ved hjælp af Merge Sort
  • Find den mindste længde Usorteret Subarray, sortering som gør det komplette array sorteret
  • Sorter en næsten sorteret (eller K-sorteret) matrix
  • Sorter n tal i området fra 0 til n^2 – 1 i lineær tid
  • Sorter et array i henhold til rækkefølgen defineret af et andet array
  • Find det punkt, hvor maksimale intervaller overlapper hinanden
  • Find en permutation, der forårsager det værste tilfælde af Merge Sort
  • Sorter vektor af par i stigende rækkefølge i C++
  • Minimumsbytter for at gøre to arrays identiske
  • Chokoladedistributionsproblem
  • Permuter to arrays, så summen af ​​hvert par er større eller lig med K
  • Bucket Sorter for at sortere en matrix med negative tal
  • Sorter en Matrix i stigende rækkefølge
  • Konverter et array til reduceret form ved hjælp af vektor af par
  • Mindste forskel Triplet fra tre arrays
  • Tjek om det er muligt at sortere et array med betinget ombytning af tilstødende tilladt

Svære problemer med sortering:

  • Find Surpasser Count for hvert element i array
  • Tæl forskellige forekomster som en undersekvens
  • Tæl minimum antal delmængder (eller delsekvenser) med fortløbende tal
  • Vælg k array-elementer, således at forskellen mellem maksimum og minimum minimeres
  • Minimum swap påkrævet for at konvertere binært træ til binært søgetræ
  • K-te mindste element efter at have fjernet nogle heltal fra naturlige tal
  • Maksimal forskel mellem frekvensen af ​​to elementer, således at element med større frekvens også er større
  • Minimumsswaps for at nå permuteret array med højst 2 positioner tilbage tilladte
  • Find ud af, om det er muligt at lave matrixelementer ens ved hjælp af et eksternt tal
  • Sorter et array efter at have anvendt den givne ligning
  • Udskriv række af strenge i sorteret rækkefølge uden at kopiere en streng til en anden

Hurtige links :

  • 'Øvningsproblemer' om sortering
  • 'Quizz' om sortering

Anbefalede:

  • Lær datastruktur og algoritmer | DSA Tutorial