logo

TechCodeview

Šķirošanas algoritmi

A Šķirošanas algoritms tiek izmantots, lai pārkārtotu doto masīvu vai elementu sarakstu atbilstoši elementu salīdzināšanas operatoram. Salīdzināšanas operators tiek izmantots, lai noteiktu jauno elementu secību attiecīgajā datu struktūrā.

Piemēram: Tālāk redzamais rakstzīmju saraksts ir sakārtots pieaugošā secībā pēc to ASCII vērtībām. Tas nozīmē, ka rakstzīme ar mazāku ASCII vērtību tiks novietota pirmajā vietā nekā rakstzīme ar augstāku ASCII vērtību.



Satura rādītājs

Kas ir šķirošana?

Šķirošana attiecas uz noteikta masīva vai elementu saraksta pārkārtošanu saskaņā ar elementu salīdzināšanas operatoru. Salīdzināšanas operators tiek izmantots, lai noteiktu jauno elementu secību attiecīgajā datu struktūrā. Kārtošana nozīmē visu elementu pārkārtošanu augošā vai dilstošā secībā.



Šķirošanas terminoloģija:

  • Šķirošana uz vietas: Tiek izmantots kārtošanas algoritms vietā pastāvīga telpa izvades iegūšanai (pārveido tikai doto masīvu). Tas kārto sarakstu, tikai mainot elementu secību sarakstā. Piemēri: atlases kārtošana, burbuļu kārtošana, ievietošanas kārtošana un kaudzes kārtošana.
  • Iekšējā šķirošana: Iekšējā kārtošana ir tad, kad visi dati tiek ievietoti galvenā atmiņa vai iekšējā atmiņa . Iekšējā šķirošanā problēma nevar pārsniegt tās apjomu. Piemērs: kaudzes kārtošana, burbuļu kārtošana, atlases kārtošana, ātrā kārtošana, čaulas kārtošana, ievietošanas kārtošana.
  • Ārējā šķirošana: Ārējā kārtošana ir tad, kad visus kārtojamos datus nevar vienlaikus ievietot atmiņā, kārtošanu sauc par ārējo kārtošanu. Ārējā kārtošana tiek izmantota lielam datu apjomam. Piemēri: sapludināšanas kārtošana, tagu kārtošana, daudzfāzu kārtošana, četru lentu kārtošana, ārējā radix kārtošana utt.
  • Stabila šķirošana: Kad tiek parādīti divi vienādi dati tas pats pasūtījums sakārtotos datos, nemainot to pozīciju, sauc par stabilu kārtošanu. Piemēri: sapludināšanas kārtošana, ievietošanas kārtošana, burbuļu kārtošana.
  • Nestabila šķirošana: Kad tiek parādīti divi vienādi dati savādāk pasūtījums sakārtotajos datos to sauc par nestabilo šķirošanu. Piemēri: ātrā kārtošana, kaudzes kārtošana, čaulas kārtošana .

Šķirošanas algoritmu raksturojums:

  • Laika sarežģītība: Laika sarežģītība, mērs, cik ilgs laiks nepieciešams algoritma palaišanai, tiek izmantots, lai klasificētu kārtošanas algoritmus. Šķirošanas algoritma sliktākā gadījuma, vidējā gadījuma un labākā gadījuma veiktspēju var izmantot, lai kvantitatīvi noteiktu procesa laika sarežģītību.
  • Kosmosa sarežģītība: Kārtošanas algoritmiem ir arī telpas sarežģītība, kas ir algoritma izpildei nepieciešamais atmiņas apjoms.
  • Stabilitāte: Šķirošanas algoritms tiek uzskatīts par stabilu, ja pēc šķirošanas tiek saglabāta vienādu elementu relatīvā secība. Tas ir svarīgi noteiktos lietojumos, kur ir jāsaglabā sākotnējā vienādu elementu secība.
  • Šķirošana uz vietas: Vietējais šķirošanas algoritms ir tāds, kam datu kārtošanai nav nepieciešama papildu atmiņa. Tas ir svarīgi, ja pieejamā atmiņa ir ierobežota vai ja datus nevar pārvietot.
  • Pielāgošanās spēja: Adaptīvais kārtošanas algoritms ir tāds, kas izmanto jau esošās datu secības priekšrocības, lai uzlabotu veiktspēju.

Šķirošanas algoritmu pielietojumi:

  • Meklēšanas algoritmi: Šķirošana bieži ir izšķirošs solis meklēšanas algoritmos, piemēram, binārajā meklēšanā, trīskāršā meklēšanā, kur dati ir jāsakārto pirms konkrēta elementa meklēšanas.
  • Datu vadība: Datu kārtošana atvieglo meklēšanu, izgūšanu un analīzi.
  • Datu bāzes optimizācija: Datu kārtošana datu bāzēs uzlabo vaicājumu veiktspēju.
  • Mašīnmācība: Kārtošana tiek izmantota, lai sagatavotu datus mašīnmācīšanās modeļu apmācībai.
  • Datu analīze: Kārtošana palīdz identificēt modeļus, tendences un novirzes datu kopās. Tam ir būtiska nozīme statistiskajā analīzē, finanšu modelēšanā un citās uz datiem balstītās jomās.
  • Operētājsistēmas: Šķirošanas algoritmi operētājsistēmās tiek izmantoti tādiem uzdevumiem kā uzdevumu plānošana, atmiņas pārvaldība un failu sistēmas organizēšana.

Šķirošanas algoritmu pamati:

  • Ievads šķirošanas paņēmienos – datu struktūras un algoritmu apmācības
  • Šķirošanas algoritma pielietojumi, priekšrocības un trūkumi
  • Kāds ir šķirošanas piemērs dzīvē?
  • Kas ir kārtošana DMR | Šķirošanas nozīme

Šķirošanas algoritmi:

Bibliotēkas ieviešana:

Vienkāršas šķirošanas problēmas:

  • Kārtot elementus pēc biežuma
  • Kārtojiet masīvu no 0, 1 un 2
  • Kārtojiet dažādās iekārtās saglabātos numurus
  • Kārtot masīvu viļņu formā
  • Pārbaudiet, vai kādi divi intervāli nepārklājas starp noteiktu intervālu kopu
  • Kā kārtot datumu masīvu programmā C/C++?
  • Virkņu šķirošana, izmantojot burbuļu kārtošanu
  • Atrodiet trūkstošos diapazona elementus
  • Kārtojiet masīvu pēc iestatīto bitu skaita
  • Kārtojiet pāra vietā esošos elementus pieaugošā un nepāra vietā dilstošā secībā
  • Kārtot masīvu, ja ir sakārtotas divas puses
  • Lielo veselo skaitļu kārtošana
  • Kārtojiet saistīto sarakstu ar 0, 1 un 2

Vidējas problēmas ar šķirošanu:

  • Inversiju skaits masīvā, izmantojot sapludināšanas kārtošanu
  • Atrodiet minimālā garuma nešķiroto apakšgrupu, kas ļauj sakārtot visu masīvu
  • Kārtot gandrīz sakārtotu (vai K sakārtotu) masīvu
  • Kārtojiet n skaitļus diapazonā no 0 līdz n^2 — 1 lineārajā laikā
  • Kārtojiet masīvu atbilstoši cita masīva noteiktajai secībai
  • Atrodiet punktu, kur pārklājas maksimālie intervāli
  • Atrodiet permutāciju, kas izraisa sapludināšanas kārtošanas sliktāko gadījumu
  • Kārtot pāru vektorus augošā secībā C++
  • Minimālais mijmaiņas darījums, lai divi masīvi būtu identiski
  • Šokolādes izplatīšanas problēma
  • Permutē divus masīvus tā, lai katra pāra summa būtu lielāka vai vienāda ar K
  • Segu kārtošana Lai kārtotu masīvu ar negatīviem skaitļiem
  • Kārtojiet matricu augošā secībā
  • Pārveidojiet masīvu samazinātā formā, izmantojot pāru vektoru
  • Mazākās atšķirības trīskāršs no trim masīviem
  • Pārbaudiet, vai ir iespējams kārtot masīvu, nosacīti apmainot blakus esošos

Grūtās šķirošanas problēmas:

  • Atrodiet katra masīva elementa pārspēku skaitu
  • Uzskaitiet atsevišķus gadījumus kā apakšsecību
  • Saskaitiet minimālo apakškopu (vai apakšsekvenču) skaitu ar secīgiem skaitļiem
  • Izvēlieties k masīva elementus tā, lai maksimālā un minimālā atšķirība tiktu samazināta līdz minimumam
  • Minimālais mijmaiņas apjoms, kas nepieciešams, lai pārveidotu bināro koku par bināro meklēšanas koku
  • K-tais mazākais elements pēc dažu veselu skaitļu noņemšanas no naturāliem skaitļiem
  • Maksimālā atšķirība starp divu elementu frekvenci tā, ka elementam ar lielāku frekvenci ir arī lielāka
  • Minimālais mijmaiņas reižu skaits, lai sasniegtu permutētu masīvu, pieļaujot ne vairāk kā 2 pozīciju mijmaiņas darījumus
  • Noskaidrojiet, vai ir iespējams padarīt masīva elementus vienādus, izmantojot vienu ārējo numuru
  • Kārtojiet masīvu pēc dotā vienādojuma piemērošanas
  • Drukājiet virkņu masīvu sakārtotā secībā, nekopējot vienu virkni citā

Ātrās saites :

  • Šķirošanas prakses problēmas
  • “Viktorīnas” par šķirošanu

Ieteicams:

  • Uzziniet datu struktūru un algoritmus | DSA apmācība