Dotaz: Setřídění pole

[Dooyer]

vysvětlí mi někdo jak to celé funguje? trošku se v tom ztrácím

---

---

Odpovědi

[Vtipnéř]

Chtělo by to upřesnit, v čem se ztrácíš. Není Ti jasné, o co jde, nebo nechápeš některý konkrétní algoritmus?

Jirka

[Dooyer]

celkově ten algoritmus si nedokážu představit, zkoušel sem si to graficky představit a nějak sem to nepobral a ty operace pod tím if ty taky nechápu

[Dooyer]

jakože chtěl bych vysvětlit postupně co tenhle seřazovací algoritmus dělá od prvního for až po ten if

[HAgriT]

Tak si nech pole po každé iteraci vypsat nebo nažhav debugger.

[Radovan]

Funguje to úplně debilně, tím snad nejhorším možným způsobem, protože v tom nejideálnějším případě počítač dělá zbytečnou práci jenom polovinu času. V reálu mnohem víc...

Proměnná i: pokud máš pole velké 100 prvků, projde se 99krát.

Proměnná j: prochází se prvky od nejspodnějšího až pod vrchní, tedy s indexy 0 až 98, a každý se porovná s tím přímo nad ním.

If: Pokud je nižší prvek větší než ten vyšší, prohodí se mezi sebou.

A znovu a znovu se procházejí i ty už dávno seřazené, pořád dokola.

To je všechno, tady to máš ve videu: https://www.youtube.com/watch?v=JffeC8lGb6I

[|🇵🇸]

Odkaz na snímek obrazovky s kódem, uložený na externím webu pro sdílení obrázků. Stallmanova noho… 🤦

Každopádně, ten algoritmus je neefektivní varianta bublinkového třídění (bubble sort). Vizualizací si nepochybně dokážeš najít bezpočet, včetně tanečního ztvárnění.

[Kit]

Pro pole se třemi prvky je bubblesort nejefektivnějším algoritmem.

[|🇵🇸]

Non sequitur.

Všimni si, že odkazovaná implementace vždycky provede n² iterací – nekontroluje, zda skutečně došlo k nějakým prohozením prvků.

[Gréta]

sem si mu tady minule stěžovala že má zdrojáček blbě formátovanej tak to asi dooyer vyřešil posvým :D ;D

prosimtě dooyere tady si mužeš přepnout takovej ten editor komentů do html a zdrojáček tam napišeš takhle mezi tyhlety dva pre

<pre class="brush: c">
zdrojáček
</pre>

já to taky hnedka nemohla najít i když je to napsaný hnedka pod tim okýnkem kam se piše text :O :O :D :D

[Vtipnéř]

Sorry, napoprvé jsem přehlédl ten odkaz na obrázek s algoritmem.

Jak už bylo uvedeno, jedná se o tzv. buble sort. Postupně se porovnávají prvky vedle sebe a když jsou ve špatném pořadí, tak se prohodí. Tak se při prvním průchodu dostane největší prvek na konec pole - probublá nahoru, odtud název. Při druhém průchodu se druhý největší prvek dostane na předposlední místo v poli a tak to jde dál.

Algoritmus je uveden neefektivně, jelikož při druhém průchodu se nemusí jít až na konec pole, stačí skončit o jeden prvek dřív, při druhém průchodu o dva prvky dřív atd.

Navíc údaj v poznámce za hlavičkou funkce je matoucí, pole je tam označeno jen "u" místo "uk" a vypadá to, že by mělo mít jen 10 prvků.

Jirka

[Dooyer]

a pro to zefektivnění to jen před cyklus for (s porovnáváním sousedů) dám např for (l=1; l<9;l++) tímpádem ten v tom cyklu for(s porovnvanim sousedu) bude změněno pocet-l.. a potom se ten pocet porovnávacích sousedů bude snizovat a bude to efektivnejsi ne? nebudou se porovnavat serazene cisla

[Gréta]

jestli ti jako rozumim tak jo ;D

takhle nějak by to mělo vypadat si myslim ale za výsledek neručim protože už sem skoro spací

 

...
for(i=0;i<pocet;i++)
{
    //nejvíc největší prvek políčka dofrčí vždycky uplně nakonec pole
    //určitě už ho jako nebudem postrkovat jinam protože větší tam neni
    //no a protože už nebudeme šahat nakonec mužeme snížit o počet průběhů 'i' páč tolik jsme už
    //umístili nejvíc největších prvků jakoby za každej ten průběh ;D
    //jo o jedničku zmenšujem protože tam máme j+1 a udělalo by to out of range vyjímku

    for(j=0;j<pocet-i-1;j++)
    {
    
        if(uk[j]>uk[j+1])
        {
            
            //prohodíme [j] s [j+1]
            pom=uk[j];
            uk[j]=uk[j+1];
            uk[j+1]=pom;
        
        }
    
    }

}
...

[Ovrscout]

Celkem pěkně je (nejen) buble sort vizualizován a posán zde: https://www.algoritmy.net/article/3/Bubble-sort

[Dooyer]

a ještě mě zajímá uk[j+1]=pom .. proč tam musí být tenhle řádek a proč by to nejelo bez něj?

[Dooyer]

myslíš v tom prohazování??

pom=uk[j];
uk[j]=uk[j+1];
uk[j+1]=pom;

nóóóó tyhlety tři řádky sloužej k prohození dvou prvků pole. na prvním řádku si do dočasný pomocný proměný schováme hodnotu prvku na pozici j. děláme to proto že na druhým řádku tu pozici j přepišeme hodnotou prvku j+1 a původní obsah na pozici j by byl uplně ztracenej :O :O ;D

no a na posledním řádku teda tu původní hodnotu prvku j schovanou teďko už jenom v tý pomocný proměný zapišeme na pozici j+1. takže co bylo nazačátku na pozici j je teďko na j+1 no a co bylo nazačátku na j+1 je na j ;D