Het artikel bespreekt enkele van de meest populaire sorteeralgoritmen voor arrays, die zowel praktisch als voor educatieve doeleinden worden gebruikt. Ik wil meteen een voorbehoud maken dat alle beschouwde algoritmen langzamer zijn dan de klassieke methode om een array door een lijst met waarden te sorteren, maar niettemin verdienen ze aandacht. Er is veel tekst, dus voor elk algoritme beschrijf ik de meest elementaire.
1. Algoritme "Sorteren op keuze".
Het is een van de eenvoudigste algoritmen voor het sorteren van arrays. Het idee is om door de array te gaan en elke keer naar het minimumelement van de array te zoeken, en dit uit te wisselen met het startelement van het ongesorteerde deel van de array. Op kleine arrays kan het zelfs effectiever zijn dan complexere sorteeralgoritmen, maar bij grote arrays verliest het in ieder geval. Het aantal elementuitwisselingen vergeleken met het "bubble"-algoritme is N/2, waarbij N het aantal array-elementen is.
Algoritme:
1. Zoek het minimumelement in de array.
2. Verwissel het minimum- en eerste element.
3. Opnieuw zoeken we naar het minimumelement in het ongesorteerde deel van de array
4. Verwissel het tweede element van de array en het minimaal gevonden element, omdat het eerste element van de array het gesorteerde deel is.
5. We zoeken naar de minimumwaarden en wisselen elementen uit totdat de array tot het einde is gesorteerd.
//Sorteren op selectie (--- Functie Sorteren op selectie (Waardematrix) Min = 0; Voor i = 0 Door Array.VBoundary() Lus Min = i; Voor j = i + 1 Door Array.VBoundary() Lus / /Zoek naar het minimumelement in array If Array[j]< Массив[Мин] Тогда Мин = j; КонецЕсли; КонецЦикла; Если Массив [Мин] = Массив [i] Тогда //Если мин. элемент массива = первому элементу неотс. части массива, то пропускаем. Продолжить; КонецЕсли; Смена = Массив[i]; //Производим замену элементов массива. Массив[i] = Массив[Мин]; Массив[Мин] = Смена; КонецЦикла; Возврат Массив; КонецФункции
2. Algoritme "Bubble sorteren".
Misschien wel het bekendste algoritme, dat voor educatieve doeleinden wordt gebruikt, is te traag voor praktisch gebruik. Het algoritme ligt ten grondslag aan complexere algoritmen: “Shaker sort”, “Piramide sort”, “Quick sort”. Het is opmerkelijk dat een van de snelste algoritmen, het ‘Fast Algorithm’, werd ontwikkeld door een van de slechtste algoritmen, ‘Bubble Sort’, te upgraden. De ‘Quick’- en ‘Shaker’-soorten zullen verder worden besproken. De betekenis van het algoritme is dat de “lichtste” elementen van de array “zweven” en de “zwaarste” elementen “zinken”. Vandaar de naam "Bubble Sort"
Algoritme:
1. Elk element van de array wordt vergeleken met het volgende en als element[i] > element wordt vervangen. Dus de "lichtste" elementen "zweven" - verplaatsen zich naar het begin van de lijst, en de zwaarste "zinken" - verplaatsen zich naar het einde.
2. Herhaal stap 1 n-1 keer, waarbij n Array.Quantity () is.
//Bubble Sort (--- Functie Bubble Sort(Waarde Array) For i = 0 By Array.InBorder() Loop For j = 0 By Array.InBorder() - i - 1 Loop If Array[j] > Array Then Replacement = Array[j];
3. Algoritme "Shaker sorteren" (Shuffle sorteren, Bidirectioneel bellen sorteren).
Het algoritme is een versie van de vorige sortering: "bubble sort". Het belangrijkste verschil is dat er bij het klassieke bellensorteren sprake is van een unidirectionele beweging van elementen van onder naar boven, terwijl bij schudsorteren de beweging eerst van onder naar boven plaatsvindt en vervolgens van boven naar beneden.
Het algoritme is hetzelfde als het sorteren van bellen + er is een top-down cyclus toegevoegd.
In het onderstaande voorbeeld is er een verbetering in het sorteren van de shaker. In tegenstelling tot de klassieke versie worden er twee keer minder iteraties gebruikt.
//Sorteren door mixen (Shaker-Sort) (--- Functie Sorteren door mixen (Waardematrix) For i = 0 BY Array.VBoundary()/2 Loop nIter = 0; conIter = Array.VBoundary(); While nIter Array [nIter+ 1] Dan Vervanging = Array[nIter]; Array[nIter] = Array[nIter + 1] = Vervanging;//Verplaats de positie één stap vooruit //Pass with end If Array[conIter - 1] > Array[conIter] Then Replacement = Array[conIter - 1]; Array[conIter]; //Verplaats de positie een stap terug EndCycle;
4. Algoritme "Dwergensortering".
Het algoritme heeft zo'n vreemde naam gekregen dankzij de Nederlandse wetenschapper Dick Grun.
Het sorteren van kabouters is gebaseerd op de techniek die wordt gebruikt door de Nederlandse tuinkabouter. Dit is de manier waarop een tuinkabouter een rij bloempotten sorteert. In essentie kijkt hij naar de volgende en vorige tuinpotten: als ze in de juiste volgorde staan, stapt hij een pot naar voren, anders verwisselt hij ze en stapt hij een pot terug. Randvoorwaarden: als er geen eerdere pot is, gaat deze naar voren; als er geen volgende pot is, is deze klaar.
Dick Grün
Dat is eigenlijk de volledige beschrijving van het "Dwarf Sorting" -algoritme. Interessant is dat het algoritme geen geneste lussen bevat, maar de hele array in één keer sorteert.
// Dwergensortering (--- Functie DwarvenSort (Waardematrix) i = 1; j = 2; Terwijl i< Массив.Количество() Цикл // Сравнение < - Сортировка по возрастанию, >- aflopend Als Array i = j; j = j + 1; Anders Vervanging = Array[i]; Array[i] = Array; Array = Vervanging; ik = ik - 1; Als ik = 0 Dan is ik = j; j = j + 1; stop als;
stop als;
Eindcyclus; Retourreeks; Eindfunctie //---)
5. Algoritme "Invoegsortering".
Dit is een eenvoudig sorteeralgoritme. Het punt is dat we bij elke stap een element nemen, er een positie voor zoeken en het op de juiste plaats invoegen.
Een elementair voorbeeld: als je voor de dwaas speelt, trek je een kaart uit de stapel en plaats je deze op de juiste plaats in oplopende volgorde van de kaarten die je hebt. Of
in de winkel gaven ze je wisselgeld voor 550 roebel - het ene biljet is 500, het andere is 50. Je kijkt in je portemonnee en er zijn biljetten in coupures van 10.100.1000. U voegt een rekening in
ter waarde van 50 roebel. tussen 10r en 100r bankbiljetten, en een biljet van 500 roebel tussen 100r en 1000r bankbiljetten. Het blijkt 10,50,100,500,1000 te zijn. Alsjeblieft
en het Insertion Sort-algoritme.< Массив Цикл Массив[j] = Массив; Замена = j - 1; Ключ = j - 1; j = j - 1; КонецЦикла; Массив[Ключ] = Замена; КонецЦикла; Возврат Массив; КонецФункции //---}
Bij elke stap van het algoritme moet u dus de gegevenssubarray sorteren en de waarde op de juiste plaats invoegen.
//Invoegsortering (--- Functie Invoegsortering (Waardematrix) Voor i = 0 Door Array.BBorder()-1 Loop Key = i + 1; Vervangen = Array[Sleutel]; j = i + 1; Terwijl j > 0 En Vervanging
6. Algoritme "Samenvoegen sorteren".
Een interessant algoritme qua implementatie en idee. De betekenis ervan is om de array in subarrays te splitsen totdat de lengte van elke subarray gelijk is aan 1. Vervolgens beweren we dat zo'n subarray is gesorteerd. Vervolgens voegen we de resulterende subarrays samen, waarbij we tegelijkertijd de waarden van de subarrays element voor element vergelijken en sorteren.
p/s Ik kon hier geen tekening invoegen met een meer visueel diagram, deze is voortdurend vlekkerig. Maar het is duidelijk zichtbaar in het onderstaande blok met screenshots. Je kunt zien hoe het algoritme werkt.< ТочкаРазрыв Тогда лМассив.Добавить(Массив[Сч]); Иначе прМассив.Добавить(Массив[Сч]); КонецЕсли; КонецЦикла; Возврат Слияние(СортировкаСлиянием(лМассив),СортировкаСлиянием(прМассив)); КонецФункции Функция Слияние(массив1,массив2) a = 0; b = 0; слМассив = Новый Массив; Для Сч = 0 ПО (Массив1.Количество() + Массив2.Количество())-1 Цикл слМассив.Добавить(); КонецЦикла; Для i = 0 ПО (массив1.Количество() + массив2.Количество())-1 Цикл Если b < массив2.Количество() И a < массив1.Количество() Тогда Если (массив1[a] >//Samenvoeg sortering (---< массив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; КонецЕсли; КонецЕсли; КонецЦикла; Возврат слМассив; КонецФункции //---}
Functie MergeSort(Waardematrix) If Array.Count() = 1 Then Return Array; stop als;
Het algoritme is vernoemd naar de Amerikaanse wetenschapper Donald Schell. In de kern is dit algoritme een verbeterd Insertion Sort-algoritme. Het doel van het algoritme is om niet alleen elementen die naast elkaar liggen, maar ook op enige afstand te vergelijken. Eerst wordt een stap geselecteerd: een bepaald interval waarover de array-elementen bij elke iteratie worden vergeleken. Het wordt meestal als volgt gedefinieerd:
Voor de eerste iteratie is Step = Object(Array.Quantity()/2), voor volgende iteraties Step = Object(Step/2). Die. geleidelijk wordt de stap verkleind en wanneer de stap gelijk is aan 1 zal de laatste vergelijking plaatsvinden en zal de array worden gesorteerd.
Voorbeeld:
Gegeven een array (10,5,3,1,14,2,7,12).
1. Stap = 4.
We sorteren op eenvoudige invoegingen elke 4 groepen van 2 elementen (10,14)(5,2)(3,7)(1,12)
10 ,2 ,3 ,1,14 ,5 ,7 ,12
2. Stap = 2
We sorteren op eenvoudige invoegingen elke 2 groepen van 4 elementen (10,3,14,7)(2,1,5,12)
3 ,1 ,7 ,2 ,10 ,5 ,14 ,12
3. Stap = 1
We sorteren door middel van eenvoudige invoegingen elk 1 groep van 8 elementen.
1,2,3,5,7,10,12,14
//Shell Sorteren (--- Functie Shell Sorteren(Waardematrix) Stap = Integer(Array.Quantity()/2); Terwijl Stap > 0 Cyclus i = 0; Terwijl i< (Массив.Количество() - Шаг) Цикл j = i; Пока j >= 0 EN Array[j] > Arraylusvervanging = Array[j]; Array[j] = Array; Array = Vervanging; j = j-1; Als ApplyDisplaySortThenDisplaySortChart(Array); stop als;
Eindcyclus; ik = ik + 1; Eindcyclus; Stap = Object(Stap/2); UserInterruptHandling(); Eindcyclus; Retourreeks; Eindfunctie //---)
8. Algoritme "Snel sorteren".
Het meest populaire en gebruikte algoritme in de praktijk. Het is een van de meest effectieve algoritmen voor het sorteren van gegevens.
De hele essentie van het algoritme komt neer op het opdelen van een complex probleem in kleine problemen en het afzonderlijk oplossen ervan. Er wordt een bepaald referentiepunt geselecteerd en alle waarden die minder zijn, worden naar links gegooid, alle andere naar rechts. Doe vervolgens voor elk ontvangen deel hetzelfde, totdat het niet meer mogelijk is om de delen te splitsen. Aan het einde krijgen we een heleboel gesorteerde onderdelen die gewoon tot één geheel moeten worden gelijmd.< m Цикл i = i + 1; КонецЦикла; Пока Массив[j] >//Algoritme "Snel sorteren" ( Procedure b_Sort(Array, LowerLimit, UpperLimit) i = LowerLimit; j = UpperLimit; m = Array[Integr((i+j)/2)]; While True Loop While Array[i]< j Тогда б_Сортировка(Массив,НижнийПредел,j); КонецЕсли; Если i < ВерхнийПредел Тогда б_Сортировка(Массив,i,ВерхнийПредел); КонецЕсли; КонецПроцедуры Функция БыстраяСортировка(Массив) НижняяГраница = 0; ВерхняяГраница = Массив.ВГраница(); б_Сортировка(Массив,НижняяГраница,ВерхняяГраница); Возврат Массив; КонецФункции //---}
m Cyclus j = j - 1; Eindcyclus; Als i > j Dan afbreken; stop als;
Eindcyclus; Als LowerLimit
//Sorteren op een lijst met waarden (--- Functie Sorteren op een lijst met waarden (Waardematrix) mlistValues = Nieuwe ListValues; mlistValues.LoadValues(Array); mlistValues.SortByValue(SortDirection.Asc); Retourneert mlistvalues.UnloadValues(); EndFunction //---)
Het sorteren kan worden versneld door de code in lussen van één regel te plaatsen. Maar voor de leesbaarheid heb ik het zo gelaten.
Ik heb een verwerking geschreven die alle bovenstaande algoritmen implementeert en ook dynamische animatie van het sorteerproces ondersteunt (Behalve standaard 1c-sortering) .
-Wanneer de verwerking begint, wordt automatisch een reeks willekeurige getallen van 0 tot 100 met een afmeting van 100 elementen gevormd.
-Om nog een array te maken, moet u op de knop "RNG-array maken" klikken. U kunt ook het gewenste bereik selecteren.
-Om dynamische animatie in te schakelen, moet u het vakje "Sortering weergeven in diagram" aanvinken. Ik raad je aan om het vakje aan te vinken voor inefficiënte algoritmen als de array maximaal 100 elementen bevat, anders ben je te oud om te wachten op sorteren :)
Dynamische weergave van het sorteerproces vermindert de prestaties aanzienlijk, maar je kunt duidelijk zien hoe het algoritme werkt.
Vroeg of laat zal elke programmeur gegevens uit een array moeten sorteren. Of het nu gaat om het weergeven van gegevens uit de database in alfabetische volgorde of het sorteren van bestandsnamen op datum van laatste wijziging, het kan dankzij de ingebouwde PHP-functies voor het sorteren van arraygegevens. In dit artikel zal ik met voorbeelden demonstreren en uitleggen hoe functies zoals sort(), rsort() werken.
Functie; - Sorteer de array in oplopende en alfabetische volgorde
Structuur:
($Array, $Flag);
De functie sorteert de array die eraan wordt gegeven $Array in oplopende volgorde. De functie is ontworpen om met lijsten te werken. Lijsten zijn gewone arrays waarvan de sleutels vanaf nul beginnen. De functie kan een optioneel argument $Flag krijgen, dat precies manipuleert wat er moet gebeuren sorteren. Bekijk de beschrijving van het $Flag-argument:
SORT_REGULAR– Standaard sorteerfunctie
SORT_NUMERIC- Getallen sorteren, oplopend
SORT_STRING- Tekenreeksen alfabetisch sorteren
Laten we een voorbeeld bekijken: we hebben een array waarin gegevens over het aantal studentenparen in verschillende studiejaren in chaotische vorm worden opgeslagen.
"; ) ?> Resultaat van het script: Cursus: 1 - 72 paren Cursus: 2 - 83 paren Cursus: 3 - 100 paren Als we de functie niet hadden toegepast, zou het resultaat van het werk als volgt zijn: Cursus: 1 - 83 paren Parcours: 2 - 100 paren Parcours: 3 - 72 paren
Sorteer op alfabet
Hieronder staat een script dat de landen van hun array alfabetisch sorteert; het tweede argument van de functie ($Flag) hoeft niet te worden ingesteld, omdat de functie zelf zal begrijpen dat hij met strings moet werken.
"; ) ?> Resultaat van het werk: Armenië Italië Rusland Japan
Functie rsort() - Sorteer een array in aflopende volgorde
De functie is onlogisch, maar sorteert arrays in aflopende volgorde. Laten we eens kijken naar de syntaxisstructuur:
($Array, $Flag);
Het voorbeeld voor deze functie zal vergelijkbaar zijn met de hierboven gegeven voorbeelden, behalve één ding: de gegevens uit de array worden in aflopende volgorde gesorteerd. We creëren een reeks prijzen voor degenen die de 1e, 2e en 3e plaats in de competitie behalen.
"; ) ?> Resultaat van de uitvoering van het script: 1e plaats - prijs: 2800 roebel. 2e plaats - prijs: 1200 roebel. 3e plaats - prijs: 500 roebel.
Bij het werken op veel sites komt vaak de vraag naar voren hoe arraygegevens in alfabetische volgorde moeten worden gesorteerd. Veel mensen schrijven hiervoor extra arrays, vergelijken grote tabellen en herhalen elke naam... Deze optie is niet de beste, hoewel we deze ook zullen overwegen. In dit artikel wil ik de eenvoudigste en kortste manier voorstellen, die, als je de handleidingen aandachtig leest, te vinden is in de documentatie.
Alfabetische array PHP
De methode is vrij eenvoudig en bestaat uit twee stappen: het instellen van de landinstelling (setlocal) en het direct sorteren van de array. Laten we een voorbeeld met opmerkingen bekijken.PHP-code
setlocale(LC_ALL, "Russisch_Rusland.1251"); // stel de landinstelling in voor Russische letters
// voorbeeld van een array waarin de woorden NIET in de juiste volgorde staan
$example=array("jar", "Boris", "bekijken", "vragenlijst", "jachtopziener", "Fedor", "vrouw", "stem");
Natcasesort($example, SORT_LOCALE_STRING); // sorteer de array ZONDER hoofdlettergevoeligheid
// OM HOOFDGEVOELIG te zijn, gebruikt u sort in plaats van natcasesort
// toon het resultaat
foreach ($voorbeeld als $key => $value)(
echo "$value "; // geef alleen woorden weer, zonder index
}
?>
Demonstratie Bronnen downloaden
In de demo kun je het script in actie zien. Als u wilt, kunt u ook het archief met het bestand downloaden.
Als uw server niet op Windows staat, moet u andere landinstellingen of meerdere tegelijk installeren:
(LC_ALL,"ru_RU.CP1251", "rus_RUS.CP1251", "Russian_Russia.1251");!}
// Druk ru_RU.CP1251 af voor FreeBSD
// Drukt rus_RUS.CP1251 af voor Linux
// Afdrukken Russian_Rusland.1251 voor Windows
Ik zal vooruitlopen op het beantwoorden van een van de vragen: de landinstelling voor Oekraïne in PHP ziet er als volgt uit:
Hoe kan ik de locale instellen voor andere coderingen in PHP?
// Installeer landinstellingen voor Windows
// Windows-codering-1251
setlocale(LC_ALL, "Russisch_Rusland.1251");
// Codering van KOI8-R
setlocale(LC_ALL, "Russisch_Rusland.20866");
// UTF-8-codering (gebruik zorgvuldig)
setlocale(LC_ALL, "Russisch_Rusland.65001");
?>
Tweede manier om een array in alfabetische volgorde te rangschikken in PHP
Als deze methode niet bij je past en je voor de moeilijke weg wilt gaan, maak dan een array als deze:PHP-code
=> een
=> b
=> binnen
=> r
=> d
=> e
=> ё
=> w
=> s
=> en
=> d
=> naar
=> l
=> m
=> n
=> ongeveer
=> blz
=> blz
=> met
=> t
=> j
=> f
=> x
=> ts
=> h
=> w
=> sch
=> ъ
=> s
=> b
=> eh
=> jij
=> ik
En herhaal de tweede array met de eerste letter.
We berekenen de eerste letter van elk array-element als volgt:
PHP-code
$city="Moskou"; // bijvoorbeeld element met index 1
$first_letter = mb_substr($stad,0,1,"UTF-8"); // pak de letter "M"
Omdat we met Russische letters werken (multi-byte-codering), is het beter om de functie te gebruiken mb_substr, en aan het einde is het beter om de codering van de variabele of arraygegevens precies aan te geven, in ons geval UTF-8.
Bedankt voor uw aandacht! Ik hoop dat de informatie nuttig was. Als je vragen hebt, schrijf dan in de reacties.
Hoe groter de reeks geanalyseerde gegevens, hoe moeilijker het is om zich te concentreren op de belangrijkste kenmerken ervan. Om de informatie in een dataset beter te begrijpen, moet deze op de juiste manier worden georganiseerd. Gebruik hiervoor een geordende array of een stengel- en bladdiagram.
Array besteld
Een geordende array (niet noodzakelijkerwijs eendimensionaal) bestaat uit een reeks gegevens die in oplopende volgorde zijn gerangschikt. De tabel (figuur 1) bevat bijvoorbeeld indicatoren voor het vijfjaarlijkse gemiddelde jaarlijkse rendement van 158 fondsen. Met geordende arrays kunt u onmiddellijk de minimum- en maximumwaarden, typische waarden en het bereik bepalen waartoe het grootste deel van de waarden behoort.
Rijst. 1. Een geordende array met gegevens over het vijfjaarlijkse gemiddelde jaarlijkse rendement van 158 fondsen gericht op snelle kapitaalgroei voor de periode van 1 januari 1997 tot 31 december 2001
Download de notitie in of formaat, voorbeelden in formaat
Het is duidelijk dat het laagste niveau van het gemiddelde jaarlijkse rendement over vijf jaar -6,1% per jaar bedraagt, en het hoogste niveau 26,3%. Bovendien varieert de gemiddelde jaarlijkse prestatie van de meeste fondsen van 5 tot 15%. Toch is het presenteren van gegevens in de vorm van een tweedimensionale array (zoals in figuur 1) niet optimaal, omdat u hiermee niet snel en eenvoudig een draaitabel kunt maken. Daarom raad ik aan om eendimensionale, verticaal geordende arrays te maken. Excel biedt verschillende opties om dit te doen.
Laten we als transversaal voorbeeld eens kijken naar de gemiddelde maandelijkse temperaturen in juli in Moskou over een periode van 130 jaar aan waarnemingen (Fig. 2).
Rijst. 2. Gemiddelde maandtemperatuur in juli in Moskou; initiële data
De eenvoudigste manier om een dataset te organiseren wordt geboden door de Excel-optie Soort. Selecteer kolommen A en B; ga naar het menu Gegevens → Sorteren (Fig. 3). Er wordt een menu geopend Sorteren. In het veld Sorteer op selecteren Gemiddelde temperatuur in juli, °C, op veld Volgorde – Oplopend. Klik OK.
Rijst. 3. Gegevens sorteren
U ontvangt een lijst gesorteerd op temperatuur (Fig. 4). Het is meteen duidelijk dat de minimale gemiddelde maandtemperatuur in juli in Moskou werd gemeten in 1904 - 14,6°C, en de hoogste - in 2010 - 26,1°C. Je herinnert je dit verschrikkelijke jaar vast nog!? Houd er rekening mee dat het vorige record met ruim 10% werd overschreden.
Rijst. 4. Bestellijst
Stam en bladeren diagram
Het stengel- en bladdiagram is hiervoor een hulpmiddel visueel het organiseren van een dataset en het analyseren van de distributie ervan. De gegevens in een diagram worden verdeeld volgens de leidende getallen, of stammen, en de volgende getallen, of bladeren. Het getal 18.9 in het stam- en bladerendiagram bestaat bijvoorbeeld uit een stam van 18 en een blad van 9 (Fig. 5). Helaas maakt Excel niet automatisch een stengel- en bladgrafiek. Daarom zullen we een handmatige procedure gebruiken. We gebruiken het gehele deel van de temperatuur als de stam, en het decimale deel als de bladeren (zie de formules op het blad "Trunk and Leaves" van het Excel-bestand; eerst heb ik het fractionele deel gemarkeerd en vervolgens de breuken uit de kolommen overgebracht naar de rijen en uiteindelijk het diagram opgemaakt om het beter zichtbaar te maken).
Rijst. 5. Stam- en bladerendiagram
Een stengel- en bladdiagram visualiseert een grote hoeveelheid informatie. Je kunt er bijvoorbeeld direct de minimale (14,6) en maximale (26,1) waarden uit bepalen. Het is te zien dat de meeste waarden binnen het bereik van 16…20°С vallen, en de waarden zelf vormen een gemiddelde van ongeveer 18°С. Er is ook een vrij brede staart in gebied b O hogere waarden.
Taken testen
- De onderstaande gegevens bevatten het aantal cheques dat door 23 banken aan hun spaarders is geretourneerd vanwege een gebrek aan saldo op de rekening. (Het minimale stortingsbedrag mag niet minder zijn dan $ 100): 26 28 20 20 21 22 25 25 18 25 15 20 18 20 25 25 22 30 30 30 15 20 29.
- Maak een stengel- en bladdiagram met de gegeven gegevens.
- Bepaal de waarde waarrond de verdeling van het aantal geretourneerde cheques is geconcentreerd.
- De onderstaande gegevens tonen de maandelijkse servicekosten (in dollars) die 26 banken hun klanten in rekening brengen als het rekeningsaldo van de klant lager is dan het minimum van $ 1.500: 12 8 5 5 6 6 10 10 9 7 10 7 7 5 0 10 6 9 12 0 5 10 8 5 5 9.
- Maak een geordende array met de opgegeven gegevens.
- Maak een stengel- en bladdiagram met de gegeven gegevens.
- Welke manier om gegevens te presenteren is informatiever? Rechtvaardig je antwoord.
- Bepaal de waarde waarrond de verdeling van de maandelijkse betalingen voor bankdiensten is geconcentreerd.
Antwoorden op testtaken
1. Zie het blad “Controll1” van het Excel-bestand en Fig. 6. Een stam-en-bladdiagram is informatiever dan een geordende array, omdat het gegevens beter visualiseert. De gemiddelde waarde is ongeveer 22. De truc van de klus is het kiezen van een stap voor de trunkwaarden. Als je als stap het aantal tientallen (10, 20, 30) kiest, verliest het diagram ‘stam en bladeren’ zijn duidelijkheid.
Sorteer een array is het proces waarbij alle elementen in een bepaalde volgorde worden verdeeld. Heel vaak is dit nuttig. Uw inbox geeft bijvoorbeeld e-mails weer op basis van het tijdstip waarop ze zijn ontvangen; nieuwe e-mails worden als relevanter beschouwd dan de e-mails die u een half uur, een uur, twee of een dag geleden heeft ontvangen; Wanneer u naar uw contactenlijst gaat, staan de namen meestal in alfabetische volgorde, omdat u dan gemakkelijker iets kunt vinden. In al deze gevallen moet de gegevens worden gesorteerd voordat deze daadwerkelijk worden uitgevoerd.
Hoe werkt sorteren?
Het sorteren van gegevens kan het zoeken binnen een array efficiënter maken, niet alleen voor mensen, maar ook voor computers. Beschouw bijvoorbeeld een geval waarin we moeten uitzoeken of een bepaalde naam in een lijst met namen voorkomt. Om dit te weten te komen, moeten we elk element van de array vergelijken met onze waarde. Het doorzoeken van een array met veel elementen kan te inefficiënt (duur) zijn.
Laten we echter aannemen dat onze reeks namen alfabetisch is gesorteerd. Dan begint onze zoektocht met de eerste letter van onze waarde en eindigt met de volgende letter in het alfabet. Als we in dit geval bij deze letter zijn aangekomen en de naam niet hebben gevonden, weten we zeker dat deze niet in de rest van de array staat, omdat we onze brief al in alfabetische volgorde hebben doorgegeven!
Het is geen geheim dat er betere algoritmen zijn voor het zoeken in gesorteerde arrays. Met behulp van een eenvoudig algoritme kunnen we zoeken naar een specifiek element in een gesorteerde array met 1.000.000 elementen met slechts 20 vergelijkingen! Het nadeel is natuurlijk dat het sorteren van een array met zo'n groot aantal elementen relatief duur is, en dat dit zeker niet wordt gedaan omwille van een enkele zoekopdracht.
In sommige gevallen maakt het sorteren van een array het zoeken overbodig. We zijn bijvoorbeeld op zoek naar de beste score van een leerling op een toets. Als de array niet is gesorteerd, moeten we elk element van de array doorzoeken om de hoogste score te vinden. Als de array is gesorteerd, staat de hoogste score op de eerste of op de laatste positie (afhankelijk van hoe de array is gesorteerd: oplopend of aflopend), dus we hoeven helemaal niet te zoeken!
Sorteren gebeurt doorgaans door paren array-elementen herhaaldelijk te vergelijken en de waarden te vervangen als ze aan bepaalde criteria voldoen. De volgorde waarin deze elementen worden vergeleken, hangt af van welk sorteeralgoritme wordt gebruikt. De criteria bestaan uit hoe de array wordt gesorteerd (bijvoorbeeld oplopende of aflopende volgorde).
Om twee elementen te verwisselen kunnen we de functie gebruiken std::wissel() uit de C++-standaardbibliotheek, die is gedefinieerd in het algoritme. In C++11 is std::swap() verplaatst naar het headerbestand van het hulpprogramma:
#erbij betrekken
#erbij betrekken #erbij betrekken int hoofd() int a = 3; int b = 5; std::uit<< "Before swap: a = " << a << ", b = " << b << "\n" ; std::wissel(a, b); // verwissel de waarden van variabelen a en b std::uit<< "After swap: a = " << a << ", b = " << b << "\n" ; |
Het resultaat van het uitvoeren van het bovenstaande programma:
Vóór de ruil: a = 3, b = 5
Na ruil: a = 5, b = 3
Na het uitvoeren van de vervangingsoperatie werden de waarden van de variabelen a en b verwisseld.
Arrays sorteren met behulp van de selectiemethode
Er zijn veel manieren om arrays te sorteren. Array-sortering op selectie is misschien het gemakkelijkst te begrijpen, maar ook een van de langzaamste.
Voor een array sorteren door van het kleinste naar het grootste element te selecteren de volgende stappen worden uitgevoerd:
Beginnend met het element op index 0, zoeken we naar de kleinste waarde in de array.
De gevonden waarde wordt verwisseld met het nulelement.
We herhalen stap nr. 1 en nr. 2 voor de volgende index in de array.
Met andere woorden: we zoeken naar het kleinste element in de array en verplaatsen dit naar de eerste plaats. Vervolgens zoeken we naar het op een na kleinste element en verplaatsen dit naar de tweede plaats na het eerste kleinste element. Dit proces gaat door totdat de array geen ongesorteerde elementen meer heeft.
Hier is een voorbeeld van hoe dit algoritme werkt in een array met 5 elementen:
{ 30, 50, 20, 10, 40 }
Eerst zoeken we naar het kleinste element, beginnend bij index 0:
{ 30, 50, 20, 10 , 40 }
Vervolgens verwisselen we het kleinste element met het element op index 0:
{ 10 , 50, 20, 30 , 40 }
Nu het eerste element van de array is gesorteerd, negeren we het. We zoeken naar het op één na kleinste element, maar beginnend bij index 1:
{ 10 , 50, 20 , 30, 40 }
En verwissel het met het element op index 1:
{ 10 , 20 , 50 , 30, 40 }
Nu kunnen we de eerste twee elementen negeren. We zoeken naar het op één na kleinste element, beginnend bij index 2:
{ 10 , 20 , 50, 30 , 40 }
En verwissel het met het element op index 2:
{ 10 , 20 , 30 , 50 , 40 }
We zoeken naar het op één na kleinste element, beginnend bij index 3:
{ 10 , 20 , 30 , 50, 40 }
En verwissel het met het element op index 3:
{ 10 , 20 , 30 , 40 , 50 }
We zoeken naar het op één na kleinste element, beginnend bij index 4:
{ 10 , 20 , 30 , 40 , 50 }
En we ruilen het met het element op index 4 (er wordt zelfvervanging uitgevoerd, d.w.z. we doen niets):
{ 10 , 20 , 30 , 40 50 }
{ 10, 20, 30, 40, 50 }
Merk op dat de laatste vergelijking altijd een enkele vergelijking zal zijn (dat wil zeggen een zelfvervanging), wat een onnodige bewerking is, dus in feite kunnen we het sorteren vóór het laatste element van de array stoppen.
Arrays sorteren met behulp van de selectiemethode in C++
Hier ziet u hoe dit algoritme wordt geïmplementeerd in C++:
#erbij betrekken
#erbij betrekken #erbij betrekken int hoofd() const int lengte = 5; // Loop door elk element van de array // (behalve de laatste, deze zal al gesorteerd zijn tegen de tijd dat we er zijn) < length - 1 ; ++ startIndex ) // De kleinsteIndex-variabele slaat de index op van de kleinste waarde die we in deze iteratie hebben gevonden // Begin met het kleinste element in deze iteratie, zijnde het eerste element (index 0) int kleinsteIndex = startIndex ; // Zoek vervolgens naar een kleiner element in de rest van de array < length ; ++ currentIndex ) // Als we een element vinden dat kleiner is dan ons kleinste element, if (array [huidigeIndex]< array [ smallestIndex ] ) // onthoud het dan kleinsteIndex = huidigeIndex; // kleinsteIndex is nu het kleinste element // Verwissel ons aanvankelijke kleinste getal met het getal dat we hebben ontdekt std::swap(array[startIndex], array[kleinsteIndex]); // Nu de hele array is gesorteerd, geeft u deze op het scherm weer voor (int index = 0; index< length ; ++ index ) std::uit<< array [ index ] << " " ; retour 0; |
Het meest verwarrende deel van dit algoritme bevindt zich in een andere lus (een geneste lus genoemd). De buitenste lus (startIndex) doorloopt de elementen één voor één (één voor één). In elke iteratie van de buitenste lus wordt de binnenste lus (currentIndex) gebruikt om het kleinste element te vinden onder de elementen die in de array achterblijven (beginnend bij startIndex + 1). kleinsteIndex houdt de index bij van het kleinste element dat door de binnenste lus wordt gevonden. Vervolgens verandert kleinsteIndex de waarde van startIndex . Ten slotte passeert de buitenste lus (startIndex) dit element en herhaalt het proces zich.
Aanwijzing: Als je problemen hebt met het begrijpen hoe het bovenstaande programma werkt, probeer het dan op een vel papier te schrijven. Schrijf de eerste (ongesorteerde) elementen van de array horizontaal op een lijn bovenaan het werkblad. Teken pijlen die aangeven welke elementen op dit moment startIndex , currentIndex en kleinsteIndex zijn. Loop handmatig door het programma en teken de pijlen opnieuw als de indices veranderen. Teken na elke iteratie van de buitenste lus een nieuwe lijn die de huidige status van de array aangeeft (de locatie van de elementen).
Het sorteren van tekst wordt uitgevoerd met hetzelfde algoritme. Wijzig gewoon het arraytype van -a in en initialiseer het met de juiste waarden.
std::sort()
Omdat de werking van sorteerarrays heel gebruikelijk is, biedt de standaardbibliotheek van C++ een ingebouwde sorteerfunctie − std::sort(). Het bevindt zich in het headerbestand van het algoritme en wordt als volgt aangeroepen:
#erbij betrekken
#erbij betrekken #erbij betrekken int hoofd() const int lengte = 5; int array [lengte] = (30, 50, 20, 10, 40); std::sort(array, array + lengte); voor (int ik = 0; ik< length ; ++ i ) std::uit<< array [ i ] << " " ; retour 0; |
Test
Taak nr. 1
Schrijf op een vel papier hoe je de volgende array kunt sorteren met behulp van de selectiemethode (zoals we hierboven hebben gedaan):
{30, 60, 20, 50, 40, 10}
Antwoord 1
30 60 20 50 40 10
10
60 20 50 40 30
10 20
60
50 40 30
10 20 30
50 40 60
10 20 30 40
50
60
10 20 30 40 50
60 (zelfvervanging)
10 20 30 40 50 60
(zelfvervanging)
Taak nr. 2
Herschrijf de programmacode vanaf de ondertitel “Arrays sorteren op selectie in C++” zodat het sorteren in aflopende volgorde gebeurt (van het grootste naar het kleinste getal). Hoewel dit op het eerste gezicht misschien ingewikkeld lijkt, is het eigenlijk heel eenvoudig.
Antwoord #2
Verander gewoon:
Als (matrix< array)
if (array [huidigeIndex]< array [ smallestIndex ] ) |
Als (array > array)
if (array [huidigeIndex] > array [kleinsteIndex] ) |
Ook kleinsteIndex moet worden hernoemd naar grootsteIndex:
#erbij betrekken
#erbij betrekken #erbij betrekken int hoofd() const int lengte = 5; int array [lengte] = (30, 50, 20, 10, 40); // Loop door elk element van de array behalve het laatste for (int startIndex = 0; startIndex< length - 1 ; ++ startIndex ) // grootsteIndex is de index van het grootste element dat we tot nu toe hebben gevonden int grootsteIndex = startIndex ; // Loop door elk element van de array, beginnend bij startIndex + 1 for (int currentIndex = startIndex + 1; currentIndex< length ; ++ currentIndex ) // Als het huidige element groter is dan ons grootste element, if (array [huidigeIndex] > array [grootsteIndex] ) // dan is dit het nieuwe grootste element in deze iteratie grootsteIndex = huidigeIndex; // Verwissel ons startnummer met het grootste gevonden element std::swap (array [startIndex], array [grootsteIndex]); // Geef de gesorteerde array op het scherm weer voor (int index = 0; index< length ; ++ index ) std::uit<< array [ index ] << " " ; retour 0; |
Taak nr. 3
Deze taak is iets moeilijker.
Een andere eenvoudige methode voor het sorteren van elementen is "bellensoort"(of meer "bellen sorteren"). Het idee is om een paar waarden in de buurt te vergelijken, en als aan de opgegeven criteria wordt voldaan, worden de waarden van dit paar verwisseld. En zo ‘borrelen’ de elementen naar het einde van de array. Hoewel er verschillende manieren zijn om het sorteren van bellen te optimaliseren, blijven we voor deze opdracht bij de niet-geoptimaliseerde versie, omdat deze eenvoudiger is.
Voor een niet-geoptimaliseerde versie van bellensortering worden de volgende stappen uitgevoerd: sorteer een array van de kleinste naar de grootste waarde:
Het array-element op index 0 wordt vergeleken met het array-element op index 1. Als het element op index 0 groter is dan het element op index 1, dan worden de waarden verwisseld.
We gaan dan naar het volgende paar waarden: het element op index 1 en het element op index 2, enzovoort totdat we het einde van de array bereiken.
Herhaal stap #1 en stap #2 totdat de hele array is gesorteerd.
Schrijf een programma dat de volgende array sorteert met behulp van bellensortering volgens de bovenstaande regels:
const int lengte(9); int array = ( 7, 5, 6, 4, 9, 8, 2, 1, 3 );
const int lengte(9); |
Aan het einde van het programma drukt u de gesorteerde elementen van de array af.
Aanwijzing: Als we slechts één element in één iteratie kunnen sorteren, betekent dit dat we de lus net zo vaak moeten herhalen als er getallen in onze array staan (de lengte ervan) om ervoor te zorgen dat de hele array wordt gesorteerd.
Antwoord #3
#erbij betrekken
#erbij betrekken #erbij betrekken int hoofd() const int lengte(9); int array [lengte] = (7, 5, 6, 4, 9, 8, 2, 1, 3); voor (int iteratie = 0; iteratie< length - 1 ; ++ iteration ) // Loop door elk array-element tot aan het laatste element (niet inclusief) // Laatste element heeft geen paar om te vergelijken for (int huidigeIndex = 0; huidigeIndex< length - 1 ; ++ huidigeIndex) { // Als het huidige element groter is dan het element erna, verwissel ze dan als(reeks[ huidigeIndex] > reeks[ huidigeIndex+ 1 ] ) soa:: ruil(reeks[ huidigeIndex] , reeks[ huidigeIndex+ 1 ] ) ; } } // Geef de gesorteerde array op het scherm weer voor(intinhoudsopgave= 0 ; inhoudsopgave< lengte; ++ inhoudsopgave) soa:: uit<< reeks[ inhoudsopgave] << " " ; opbrengst0 ; } |
Taak nr. 4
Implementeer de volgende twee optimalisatieoplossingen voor het bellensorteeralgoritme dat je in de vorige opdracht hebt geschreven:
Merk op dat elke keer dat het sorteren van bellen wordt uitgevoerd, de grootste waarde in de array naar het einde “bubbelt”. Na de eerste iteratie is het laatste element van de array al gesorteerd. Na de tweede iteratie wordt het voorlaatste element van de array gesorteerd, enzovoort. Bij elke nieuwe iteratie hoeven we elementen die al zijn gesorteerd niet opnieuw te controleren. Pas uw lus aan zodat u elementen die al zijn gesorteerd niet opnieuw controleert.
