Tietojen lajittelumenetelmät - esitys. Lajittelumenetelmät

Tässä artikkelissa käsitellään matriisien lajittelun algoritmeja. Aluksi testaukseen valitut algoritmit esitetään lyhyt kuvaus heidän työstään, minkä jälkeen testaus suoritetaan suoraan, jonka tulokset syötetään taulukkoon ja tehdään lopulliset johtopäätökset.

Lajittelualgoritmeja käytetään hyvin laajalti ohjelmoinnissa, mutta joskus ohjelmoijat eivät edes ajattele, mikä algoritmi toimii parhaiten ("parhaan" käsite tarkoittaa sekä kirjoituksen että suorituksen nopeuden ja monimutkaisuuden yhdistelmää).

Tässä artikkelissa yritämme selvittää. Parhaan tuloksen saamiseksi kaikki esitetyt algoritmit lajittelevat 200 elementin kokonaislukumallin. Tietokoneella, jolla testaus suoritetaan, on seuraavat ominaisuudet: AMD A6-3400M 4x1,4 GHz -prosessori, 8 Gt RAM-muistia, Windows 10 x64 -rakenne 10586.36 -käyttöjärjestelmä.

Tutkimukseen valittiin seuraavat lajittelualgoritmit:

Valintalaji - Algoritmin ydin on kulkea matriisi alusta loppuun etsimällä matriisin minimielementtiä ja siirtää se alkuun. Tällaisen algoritmin monimutkaisuus on O (n2).

Kuplalaji - tämä algoritmi vaihtaa kaksi vierekkäistä elementtiä, jos ryhmän ensimmäinen elementti on suurempi kuin toinen. Näin tapahtuu, kunnes algoritmi vaihtaa kaikki lajittelemattomat kohteet. Tämän lajittelualgoritmin monimutkaisuus on O (n ^ 2).

Lisälaji - algoritmi lajittelee matriisin läpi sen elementtien. Kussakin iteraatiossa otetaan elementti ja verrataan kutakin elementtiä jo lajitellussa matriisin osassa, jolloin löydetään "oma paikka", jonka jälkeen elementti lisätään paikalleen. Tämä tapahtuu, kunnes algoritmi kulkee koko taulukon läpi. Lähtö on lajiteltu taulukko. Tämän algoritmin monimutkaisuus on O (n ^ 2).

Nopea lajittelu - Algoritmin ydin on jakaa matriisi kahteen alaryhmään, keskirivi on elementti, joka on matriisin keskellä. Algoritmin toiminnan aikana keskimääräistä pienemmät elementit siirretään vasemmalle ja suuret oikealle. Sama toiminto tapahtuu rekursiivisesti aliryhmästä, ne jaetaan vielä kahteen aliryhmään, kunnes on jotain jaettavaa (yksi elementti on jäljellä). Lähtö on lajiteltu taulukko. Algoritmin monimutkaisuus riippuu syötetiedoista ja on parhaimmillaan O (n × 2log2n). Pahin tapaus O (n ^ 2). On myös keskiarvo, joka on O (n × log2n).

Kampan lajittelu - Algoritmin idea on hyvin samanlainen kuin vaihtolajittelu, mutta tärkein ero on, että ei verrata kahta naapurielementtiä, vaan elementtejä aikavälillä, esimerkiksi viidessä elementissä. Näin vältetään eroon pienistä arvoista lopussa, mikä auttaa nopeuttamaan lajittelua suurissa ryhmissä. Ensimmäinen iterointi suoritetaan vaiheella, joka lasketaan kaavalla (matriisin koko) / (pelkistyskerroin), jossa pelkistyskerroin on noin 1,247330950103979 tai pyöristetty arvoon 1,3. Toinen ja sitä seuraavat iteraatiot suoritetaan vaiheella (nykyinen vaihe) / (vähennyskerroin) ja jatkuvat, kunnes vaihe on yhtä suuri. Lähes joka tapauksessa algoritmin monimutkaisuus on O (n × log2n).

Testausta varten suoritetaan 5 ajoa kustakin algoritmista ja valitaan paras aika. Paras käytetty aika ja muisti tallennetaan taulukkoon. Testataan myös 10, 50, 200 ja 1000 elementin matriisin lajittelunopeus sen määrittämiseksi, mihin tehtäviin tietty algoritmi on tarkoitettu.

Täysin lajittelematon taulukko:

Osittain lajiteltu taulukko (puolet elementeistä on järjestetty):

Tulokset esitetään kaavioina:

Tutkimuksen ja saatujen tietojen perusteella lajittelemattoman taulukon lajittelua varten optimaalisin esitetyistä algoritmeista taulukon lajittelemiseksi on nopea lajittelu. Pidemmästä toteutusajasta huolimatta algoritmi kuluttaa vähemmän muistia, mikä voi olla tärkeää suurissa projekteissa. Algoritmit, kuten valinta, vaihto ja lisäyslajittelu, voivat kuitenkin soveltua paremmin tieteellisiin tarkoituksiin, kuten opetukseen, joissa ei tarvitse käsitellä valtavia määriä tietoa. Osittain lajitellun taulukon tulokset eivät ole kovin erilaisia, kaikki lajittelualgoritmit osoittavat aikaa noin 2-3 millisekuntia vähemmän. Kun lajitellaan osittain lajiteltu taulukko, pikalajitelma on paljon nopeampi ja käyttää vähemmän muistia.

Artikkelissa käsitellään joitain suosituimpia taulukoiden lajittelualgoritmeja, joita käytetään sekä käytännössä että opetustarkoituksiin. Haluan tehdä varauksen heti, että kaikki tarkastellut algoritmit ovat hitaampia kuin menetelmä, jolla taulukko lajitellaan klassisen arvolistan kautta, mutta ne ansaitsevat kuitenkin huomion. Saan paljon tekstiä, joten kuvaan kullekin algoritmille perustavanlaatuisimmat.

1. Algoritmi "Lajittele valinnan mukaan".

Se on yksi yksinkertaisimmista taulukon lajittelualgoritmeista. Tarkoitus on käydä matriisin läpi ja etsiä aina matriisin vähimmäiselementti, vaihtamalla se matriisin lajittelemattoman osan alkuelementin kanssa. Pienillä matriiseilla se voi olla jopa tehokkaampi kuin monimutkaisemmat lajittelualgoritmit, mutta joka tapauksessa se häviää suurilla matriiseilla. Elementtien vaihdon lukumäärä "kupla" -algoritmiin nähden on N / 2, missä N on matriisielementtien lukumäärä.

Algoritmi:
1. Etsi matriisin vähimmäisosa.
2. Muuta minimin ja ensimmäisen elementin paikkoja paikoissa.
3. Etsimme jälleen minimielementtiä taulukon lajittelemattomasta osasta
4. Korvaa matriisin toinen elementti ja löydetty minimi, koska matriisin ensimmäinen elementti on lajiteltu osa.
5. Etsi minimiarvot ja vaihda elementtejä, kunnes taulukko on lajiteltu loppuun asti.

// Lajittele valinnan mukaan (--- Toiminto Lajittele Lajittele valinnan mukaan (Arvotaulukko) Min \u003d 0; Jos i \u003d 0 Matriisin mukaan.Raja () Sykli Min \u003d i; Jos j \u003d i + 1 Matriisin mukaan.Raja () Silmukka / / Etsitään matriisin minimielementtiä Jos taulukko [j]< Массив[Мин] Тогда Мин = j; КонецЕсли; КонецЦикла; Если Массив [Мин] = Массив [i] Тогда //Если мин. элемент массива = первому элементу неотс. части массива, то пропускаем. Продолжить; КонецЕсли; Смена = Массив[i]; //Производим замену элементов массива. Массив[i] = Массив[Мин]; Массив[Мин] = Смена; КонецЦикла; Возврат Массив; КонецФункции

2. Algoritmi "Bubble sort".

Ehkä tunnetuin algoritmi, jota käytetään opetustarkoituksiin, on liian hidas käytännön käyttöön. Algoritmi on monimutkaisempien algoritmien taustalla: "Shaker Sort", "Heap Sort", "Quick Sort". On huomionarvoista, että yksi nopeimmista algoritmeista "Nopea algoritmi" kehitettiin päivittämällä yksi pahimmista algoritmeista "Bubble Sort". "Nopea" ja "Shaker" -lajikkeista keskustellaan myöhemmin. Algoritmin tarkoitus on, että matriisin "kevyimmät" elementit näyttävät "kelluvan" ja "raskaimmat" "uppoavat". Siksi nimi "Bubble Sort"

Algoritmi:
1. Matriisin kutakin elementtiä verrataan seuraavaan ja jos elementti [i]\u003e korvataan. Siten "kevyimmät" elementit "kelluvat" - siirtyvät luettelon alkuun ja raskain "pesuallas" - siirtyvät loppuun.
2. Toista vaihe 1 n-1 kertaa, jossa n on Array.Määrä ().

// Bubble Sort (--- Funktio Bubble Sort (Value Array) For i \u003d 0 Array.Boundary () Loop For j \u003d 0 Array.Boundary () - i - 1 Loop If Array [j]\u003e Array Then Replacement \u003d Array [j]; Array [j] \u003d Array; Array \u003d Korvaa; EndIf; EndLoop; EndLoop; Return Array; EndFunction // ---)

3. "Shaker sort" -algoritmi (Satunnainen lajittelu, Kaksisuuntainen kuplalajittelu).

Algoritmi on yksi edellisen lajittelun - "kupla lajittelu" - versioista. Tärkein ero on, että klassisessa kuplalajittelussa elementit liikkuvat alhaalta ylöspäin yhteen suuntaan, kun taas ravistimen lajittelussa ensin liikutaan alhaalta ylöspäin ja sitten ylhäältä alas.

Algoritmi on sama kuin kuplalajittelussa + ylhäältä alas -jakso lisätään.

Alla olevassa esimerkissä ravistimen luokittelu on parantunut. Toisin kuin klassinen, se käyttää kaksi kertaa vähemmän iteraatioita.

// Lajittele satunnaistoisto (Shaker-Lajittele) (--- Funktio SortShuffle (Taulukon arvo) Jos i \u003d 0 PO Array.Boundary () / 2 Loop nIter \u003d 0; conIter \u003d Array.Boundary (); Vaikka nIter Array [nIter + 1] Sitten Korvaus \u003d Taulukko [nIter]; Taulukko [nIter] \u003d Taulukko [nIter + 1]; Taulukko [nIter + 1] \u003d Korvaus; EndIf; nIter \u003d nIter + 1; // Siirrä paikkaa yksi askel eteenpäin // Siirry loppu Jos Array [conIter - 1]\u003e Array [conIter] Sitten Replacement \u003d Array [conIter - 1]; Array [conIter-1] \u003d Array [conIter]; Array [conIter] \u003d Replacement; EndIf; conIter \u003d conIter - 1 ; // Siirrä asemaa yksi askel taaksepäin Silmukan loppu; Silmukan loppu; Palautusryhmä; Lopetustoiminto // ---)

4. Algoritmi "Kääpiölajittelu".

Algoritmi on niin oudosti nimetty hollantilaisen tutkijan Dick Grunin ansiosta.

Kääpiölajittelu perustuu tekniikkaan, jota hollantilainen puutarhatonttu (hollantilainen tuinkabouter) käyttää. Tätä menetelmää puutarhatonttu lajittelee kukkaruukut. Pohjimmiltaan hän tarkastelee seuraavaa ja edellistä puutarhaa: jos ne ovat oikeassa järjestyksessä, hän astuu eteenpäin yhden potin, muuten hän vaihtaa ne ja astuu yhden potin takaisin. Rajaolosuhteet: jos edellistä pottia ei ole, se siirtyy eteenpäin; jos ei ole seuraavaa pottia, hän on valmis.
Dick Grun

Se on itse asiassa "Dwarven sorting" -algoritmin koko kuvaus. Mielenkiintoista on, että algoritmi ei sisällä sisäkkäisiä silmukoita, vaan lajittelee koko matriisin yhdellä kertaa.

// Dwarf Sort (--- Dwarven Sort Function (Value Array) i \u003d 1; j \u003d 2; Vaikka i< Массив.Количество() Цикл // Сравнение < - Сортировка по возрастанию, > - laskeva Jos taulukko i \u003d j; j \u003d j + 1; Muuten Korvaus \u003d Taulukko [i]; Taulukko [i] \u003d Taulukko; Taulukko \u003d Korvaa; i \u003d i - 1; Jos i \u003d 0, niin i \u003d j; j \u003d j + 1; Loppu Jos; Loppu Jos; Syklin loppu; Return Array; EndFunction // ---)

5. Algoritmi "Lajittele inserttien mukaan".

Se on yksinkertainen lajittelualgoritmi. Asia on, että jokaisessa vaiheessa otamme elementin, etsimme sen sijainnin ja asetamme sen oikeaan paikkaan.
Alkuesimerkki: Pelatessasi hölmöä, vedät kortin kannelta ja työnnät sen oikeaan paikkaan nousevassa järjestyksessä sinulla olevissa korteissa. Tai
myymälässä he antoivat sinulle 550 ruplaa - yhden 500, toisen 50 setelin. Katsot lompakkoon, ja seteleitä on 10 100 1000. Lisää lasku
arvoinen 50 ruplaa. 10r- ja 100r-seteleiden välillä ja 500-ruplaisten 100--1000r-setelien välillä. Tulee 10,50,100,500,1000 - Tässä on sinulle
ja "Lajittelu lisäysten mukaan" -algoritmi.
Siksi algoritmin jokaisessa vaiheessa sinun on lajiteltava tietojen alikartta ja lisättävä arvo oikeaan paikkaan.

6. Algorim "Yhdistä lajittelu".

Mielenkiintoinen algoritmi toteutuksen ja idean kannalta. Sen tarkoitus on jakaa matriisi aliriveihin, kunnes kunkin alirakenteen pituus on yhtä suuri kuin 1. Sitten väitämme, että tällainen alirakenne on lajiteltu. Sitten yhdistetään saadut alirakenteet yhteen ja verrataan ja lajitellaan alirakenteiden arvoja samanaikaisesti elementtien mukaan.

p / s ei voinut lisätä tähän kuvaa, jossa olisi visuaalisempi kaavio, se tahriintuu jatkuvasti. Mutta se näkyy selvästi alla olevassa kuvakaappauksissa. Näet kuinka algoritmi toimii.

// Lajittele yhdistämisen mukaan (---

Funktio SortMerge (Value Array) Jos Array.Number () \u003d 1 Sitten Return Array; Loppu Jos; Katkaisupiste \u003d Taulukon numero () / 2; lArray \u003d Uusi taulukko; prArray \u003d Uusi taulukko; Jos Mf \u003d 0 PO Array.Boundary () -sykli Jos Mf< ТочкаРазрыв Тогда лМассив.Добавить(Массив[Сч]); Иначе прМассив.Добавить(Массив[Сч]); КонецЕсли; КонецЦикла; Возврат Слияние(СортировкаСлиянием(лМассив),СортировкаСлиянием(прМассив)); КонецФункции Функция Слияние(массив1,массив2) a = 0; b = 0; слМассив = Новый Массив; Для Сч = 0 ПО (Массив1.Количество() + Массив2.Количество())-1 Цикл слМассив.Добавить(); КонецЦикла; Для i = 0 ПО (массив1.Количество() + массив2.Количество())-1 Цикл Если b < массив2.Количество() И a < массив1.Количество() Тогда Если (массив1[a] > taulukko2 [b]) JA (b< массив2.Количество()) Тогда слМассив[i] = массив2[b]; b = b + 1; Иначе слМассив[i] = массив1[a]; a = a + 1; КонецЕсли; Иначе Если b < массив2.количество() Тогда слМассив[i] = массив2[b]; b = b + 1; Иначе слМассив[i] = массив1[a]; a = a + 1; КонецЕсли; КонецЕсли; КонецЦикла; Возврат слМассив; КонецФункции //---}

7. Algorim "Kuoren lajittelu".

Algoritmi on nimetty amerikkalaisen tutkijan Donald Schellin mukaan. Ytimessä tämä algoritmi on parannettu Insert Sort -algoritmi. Algoritmin tarkoitus on verrata paitsi vierekkäisten elementtien lisäksi myös tietyllä etäisyydellä olevia elementtejä. Ensin valitaan vaihe - tietty intervalli, jonka läpi taulukkoelementtejä verrataan kullakin iteraatiolla. Se määritellään yleensä seuraavasti:
Ensimmäisessä iterointivaiheessa \u003d kokonaisluku (Array.Quantity () / 2), seuraavassa iterointivaiheessa \u003d kokonaisluku (vaihe / 2). Nuo. vaihetta pienennetään vähitellen ja kun vaihe on yhtä suuri kuin 1, viimeinen vertailu tapahtuu ja taulukko lajitellaan.

Esimerkki:
Annetaan taulukko (10,5,3,1,14,2,7,12).
1. Vaihe \u003d 4.
Lajittele yksinkertaisilla lisäyksillä jokainen 4 elementin ryhmää (10.14) (5.2) (3.7) (1.12)

10 ,2 ,3 ,1,14 ,5 ,7 ,12

2. Vaihe \u003d 2
Lajittele yksinkertaisilla lisäyksillä jokainen 4 elementin ryhmä (10,3,14,7) (2,1,5,12)

3 ,1 ,7 ,2 ,10 ,5 ,14 ,12

3. Vaihe \u003d 1
Lajittelemme yksinkertaisilla lisäyksillä jokainen 8 elementin ryhmä.

1,2,3,5,7,10,12,14

8. Algoritmi "Nopea lajittelu".

Suosituin ja käytetyin algoritmi käytännössä. Se on yksi tehokkaimmista tietojen lajittelualgoritmeista.
Algoritmin koko tarkoitus on hajottaa monimutkainen ongelma pieniksi ja ratkaista ne erikseen. Tietty vertailupiste valitaan ja kaikki pienemmät arvot heitetään vasemmalle, kaikki muut oikealle. Lisäksi se tekee jokaiselle saadulle osalle saman, kunnes osia ei ole enää mahdollista jakaa. Loppujen lopuksi saamme paljon lajiteltuja osia, jotka meidän on vain liimattu yhteen kokonaisuuteen.

// Algoritmi "Nopea lajittelu" (menettely b_Sort (matriisi, alaraja, yläraja) i \u003d alaraja; j \u003d ylempi raja; m \u003d matriisi [kokonaisluku ((i + j) / 2)]; tosisyklin aikana [i]< m Цикл i = i + 1; КонецЦикла; Пока Массив[j] > m sykli j \u003d j - 1; Syklin loppu; Jos i\u003e j Sitten keskeytä; Loppu Jos; Syklin loppu; Jos alaraja< j Тогда б_Сортировка(Массив,НижнийПредел,j); КонецЕсли; Если i < ВерхнийПредел Тогда б_Сортировка(Массив,i,ВерхнийПредел); КонецЕсли; КонецПроцедуры Функция БыстраяСортировка(Массив) НижняяГраница = 0; ВерхняяГраница = Массив.ВГраница(); б_Сортировка(Массив,НижняяГраница,ВерхняяГраница); Возврат Массив; КонецФункции //---}

9. Taulukon klassinen lajittelu 1 sekunnissa.

Välitämme taulukon arvoluettelolle. Lajittele tavallisella "Lajittele" -menetelmällä.

// Lajittelu arvoluettelon mukaan (--- Funktio Lajittelu arvoluettelon mukaan (ArrayValue) mListVal \u003d NewList ofValues; mListValues.ListValues \u200b\u200b(Array); mListValues.SortBy Value (Lajittelusuunta.Activate); Return mDownloadListValues.Value.

Kaikenlaisia \u200b\u200bvoidaan nopeuttaa järjestämällä koodi silmukoiksi yhdelle riville. Mutta luettavuuden vuoksi jätin sen niin.

Kirjoitettu käsittely, jossa kaikki yllä olevat algoritmit on toteutettu, myös lajitteluprosessin dynaamista animaatiota tuetaan (Paitsi tavallinen 1c-lajittelu) .

-Käsittelyn alkaessa luodaan automaattisesti joukko satunnaisia \u200b\u200blukuja 0-100, joiden koko on 100 elementtiä.
-Luo toinen taulukko napsauttamalla "Luo RNG-taulukko" -painiketta, voit myös valita tarvittavan alueen.
-Jos haluat ottaa dynaamisen animaation käyttöön, valitse "Näytä lajittelu kaaviossa" -valintaruutu. Kehotan sinua valitsemaan tehottomien algoritmien valintaruudun, kun matriisimitta on enintään 100 elementtiä, muuten olet vanha odottamaan lajittelua :)

Lajitteluprosessin dynaaminen renderointi vähentää huomattavasti suorituskykyä, mutta voit selvästi nähdä, kuinka algoritmi toimii.

Johdanto .

Noin kolme ja puoli vuosikymmentä on kulunut tietokoneohjelmoinnin käyttöönotosta akateemisena tieteenalana pedagogisissa yliopistoissa. Koska itse aiheen valtava muutosnopeus ylitti aina merkittävästi keskitettyjen julkaisumekanismien määrän, erityisesti pedagogisten yliopistojen ohjelmille suunnattuja kirjoja julkaistiin enintään kerran vuosikymmenessä - melkein suhteessa tietokoneiden sukupolvien muutosnopeuteen. Nykyään kirjakaupan hyllyt ovat täynnä tietojenkäsittelytieteen julkaisuja. Opettaja (ja ennen kaikkea opiskelija) tarvitsee kuitenkin erityisiä oppikirjoja, joiden sisältö ja suunta vastaavat ilmoitettua opetussuunnitelmaa ja ohjelmaa. Joidenkin erikoisalojen ohjelmoinnin lisäksi pedagogiset yliopistot ovat ottaneet käyttöön muita monimutkaisempia erikoiskursseja soveltavan (erillisen) matematiikan ja tietojenkäsittelytieteen risteyksessä.

Tässä kurssityössä voit tutustua matriiseihin ja oppia yksinkertaisista ja monimutkaisista menetelmistä niiden lajittelemiseksi sekä siitä, mitkä niistä ovat tehokkaimpia ja missä tapauksissa.

1. Tehtävien lajittelu.

1.1 Yleiset säännökset.

Päätehtävänä on esitellä erilaisia \u200b\u200blajittelumenetelmiä ja korostaa tehokkaimpia. Lajittelu on melko hyvä esimerkki ongelmasta, joka voidaan ratkaista monilla eri algoritmeilla. Jokaisella niistä on omat edut ja haitat, ja sinun on valittava algoritmi ongelman erityisen muotoilun perusteella.

Yleensä lajittelun tulisi olla prosessi, jolla tietty objektijoukko järjestetään uudelleen tietyssä järjestyksessä. Lajittelun tarkoituksena on helpottaa kohteiden löytämistä myöhemmin tällaisesta lajitellusta joukosta. Tämä on melkein universaali, perustoiminta. Tapaamme lajiteltuja esineitä puhelinluetteloissa, tuloverolistoissa, kirjojen sisältöluettelossa, kirjastoissa, sanakirjoissa, varastoissa - melkein kaikkialta, mistä meidän on etsittävä tallennettuja esineitä.

Siten lajittelusta puhuminen on varsin tarkoituksenmukaista ja tärkeää tietojen käsittelyssä. Alun perin kiinnostuksemme lajitteluun perustuu siihen tosiasiaan, että kohtaamme monia hyvin perustavanlaatuisia temppuja algoritmeja rakennettaessa. Melkein ei ole menetelmiä, joita sinun ei tarvitse tavata keskustellessasi tästä ongelmasta. Erityisesti lajittelu on ihanteellinen kohde valtavan monien algoritmien esittelyyn, ne kaikki on keksitty samaan ongelmaan, monet ovat jossakin mielessä optimaalisia, useimmilla on omat etunsa. Siksi se on myös ihanteellinen kohde, joka osoittaa tarpeen analysoida algoritmien suorituskykyä. Lisäksi esimerkit lajittelusta voivat osoittaa, kuinka monimutkaisella algoritmilla voit saavuttaa merkittävän hyötysuhteen, vaikka käytettävissä on jo ilmeisiä menetelmiä.

Algoritmin valinta riippuu käsiteltävän datan rakenteesta - tämä on melkein laki, mutta lajittelun tapauksessa tällainen riippuvuus on niin syvä, että vastaavat menetelmät jaettiin kahteen luokkaan - taulukoiden lajittelu ja tiedostojen (sekvenssit) lajittelu ). Joskus niitä kutsutaan sisäiseksi ja ulkoiseksi lajitteluksi, koska taulukot tallennetaan koneen nopeaan, satunnaismuistiin ja tiedostot sijaitsevat yleensä hitaammassa, mutta myös kapeammassa ulkoisessa muistissa mekaanisiin liikkeisiin perustuvilla laitteilla (levyt tai nauhat) ...

Oletetaan, että elementtityypiksi määritetään INTEGER.

Constn \u003d ???; // taulukon vaadittu pituus ilmoitetaan tässä

Muuttuja A: kokonaisluku;

INTEGERin valinta on jonkin verran mielivaltainen. Voisit ottaa ja

toinen tyyppi, jolle määritetään yleinen järjestyssuhde.

Lajittelumenetelmää kutsutaan pysyväksi, jos lajitteluprosessi ei muuta elementtien suhteellista sijaintia samoilla avaimilla. Vakauden lajittelu on usein toivottavaa, kun on kyse tuotteista, jotka on jo järjestetty (lajiteltu) jonkin toissijaisen avaimen (eli ominaisuuksien) perusteella, jotka eivät vaikuta ensisijaiseen avaimeen.

1.2. Lausunto matriisien lajittelun ongelmasta.

Tärkein ehto: valitun taulukoiden lajittelutavan tulisi käyttää käytettävissä olevaa muistia säästeliäästi. Tämä merkitsee sitä, että elementtien järjestyksen suorittavat permutaatiot tulisi suorittaa samassa paikassa, toisin sanoen menetelmät, joissa elementit ryhmästä a siirretään tuloksena olevaan ryhmään b, ovat paljon vähemmän kiinnostavia. Luokitellaan ensin menetelmät niiden kustannustehokkuuden mukaan, toisin sanoen niiden käyttöajan mukaan. Hyvä tehokkuuden mitta voi olla C, tarvittavien avainvertailujen määrä ja M, elementtisiirtojen määrä (permutaatiot). Nämä luvut ovat n: n funktioita - lajiteltavien elementtien lukumäärä. Vaikka hyvät lajittelualgoritmit vaativat n * logn-vertailun järjestyksen, hajotetaan ensin muutama yksinkertainen ja ilmeinen menetelmä, nimeltään suora, missä järjestys n2-avaimen vertailuja vaaditaan. Seuraavat syyt pakottavat meidät jäsentämään suorilla menetelmillä koskematta nopeisiin algoritmeihin:

1. Suorat menetelmät ovat erityisen hyödyllisiä selittäessä useimpien lajittelun perusperiaatteita.

2. Näiden menetelmien ohjelmat ovat helposti ymmärrettäviä ja lyhyitä.

3. Monimutkaiset menetelmät vaativat suuren määrän operaatioita, ja siksi riittävän pienelle n: lle suorat menetelmät osoittautuvat nopeammin, vaikka niitä ei tietenkään pitäisi käyttää suurille n: lle.

Paikalliset lajittelumenetelmät voidaan jakaa kolmeen pääluokkaan niitä määrittelevien periaatteiden mukaisesti:

· Lajittelu sisällyttämisen mukaan (lisääminen).

· Lajittelu käyttämällä valintaa (byselection).

· Lajittelu pörssien avulla (byexchange).

Tutkimme nyt näitä periaatteita ja vertaamme niitä. Kaikki ohjelmat toimivat taulukossa a.

Constn \u003d<длина массива>

a: kokonaisluku;

2. Taulukoiden lajittelumenetelmät.

2.1. Yksinkertaiset menetelmät taulukoiden lajittelussa.

2.1.1. Lajittelu suoran sisällyttämisen mukaan.

Tätä menetelmää käytetään laajasti kortteja pelattaessa. Elementit on henkisesti jaettu "valmiiksi" jaksoksi a

OHJELMA 2.1. Lajittelu suoran mukaan ottamisen mukaan.

I, J, N, X: INTEGER;

A: INTEGERIN ARRAY;

WRITELN ('Syötä taulukon pituus');

WRITELN ('Anna taulukko');

SINUN I: \u003d 1 TO N LUE (A [I]);

SINUN I: \u003d 2 TO N DO

X: n aikana

WRITELN ("Tulos:");