Diskuze – Lekce 1 - Selection sort

Zpět

Upozorňujeme, že diskuze pod našimi online kurzy jsou nemoderované a primárně slouží k získávání zpětné vazby pro budoucí vylepšení kurzů. Pro studenty našich rekvalifikačních kurzů nabízíme možnost přímého kontaktu s lektory a studijním referentem pro osobní konzultace a podporu v rámci jejich studia. Toto je exkluzivní služba, která zajišťuje kvalitní a cílenou pomoc v případě jakýchkoli dotazů nebo projektů.

Komentáře

Jarda

Člen

Jarda:14.1.2023 23:21

Zdravim pany programatory, jeste moc nezvladam casovou narocnost algorytmu, nevi nekdo jaky je rozdil v casove narocnosti mezi timto algorytmem a timhle?
Pozn. Na nocni jsem si precetl prvni dve vety popisu a hned jsem se na to vrhl, proto na zacatku nehleda minimalni hodnotu od zacatku(napsano na mobilu v aplikaci sololearn.)

Veskera kritika vitana.

int[] arr={2,1,9,5,3,44,8,6,7};

      int temp=0;
      int min=0;
      int tempJ=1;
      for(int i=0;i<arr.length;i++){
          for(int j=tempJ;j<arr.length;j++){
              min=arr[i];
              if(min>arr[j]){
                  temp=arr[i];
                  arr[i]=arr[j];
                  arr[j]=temp;
              }
          }
          tempJ++;
      }

   for(int i: arr){
       System.out.print(i+" ");
   }

Editováno 14.1.2023 23:22

Odpovědět

14.1.2023 23:21

DarkCoder

Člen

DarkCoder:14.1.2023 23:52

Jedná se o implementaci Selection Sortu v vzestupném pořadí. Složitost tohoto kódu je O(n²).

Odpovědět

14.1.2023 23:52

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Jindřich Kopáček

Člen

Jindřich Kopáček:30.1.2024 12:22

Ahoj, asi to není originální nápad, ale zkusil jsem ve vnitřním cyklu najít minimum i maximum a pak prohodit oba krajní prvky a takhle to zužovat z obou stran. Průchodů je pak půlka a zkracují se po 2.

Odpovědět

30.1.2024 12:22

Ladislav Schnaiberg

Lektor

Ladislav Schnaiberg:4.9.2024 20:33

idea-algoritmu-efektivni-selection-sort 😀

Odpovědět

4.9.2024 20:33

Yveta Kršková

Člen

Yveta Kršková:21. června 23:05

JS, více srovnávání, méně záměn v řadě v selection sortu. Ráda bych věděla prosím časovou složitost. Je časová složitost algoritmu směrodatná z hlediska aplikace na určitý hardware, totiž jestli výkon při výpočtech nezávisí spíš na technicky pro daný stroj přirozeném způsobu a postupu zpracování dat?

let delkaRad =radaCisel.length;
let indexNalCisla;
    let cisloVRuce;
    if (delkaRad > 1 && delkaRad != null) {
        for (let i = 0; i < delkaRad-1; i++) {
            indexNalCisla = i;
            for (let j = i+1; j < delkaRad; j++) {
                    if (radaCisel[i] < radaCisel[j]) {
                        if(radaCisel[indexNalCisla]<radaCisel[j]){
                        //namísto od dvou pozic v řadě se přepíše jen index nalezeného čísla
                        indexNalCisla = j;
                        }
                    }
            }
            if(indexNalCisla > i){
                cisloVRuce = radaCisel[indexNalCisla];
                radaCisel[indexNalCisla] = radaCisel[i];
                radaCisel[i] = cisloVRuce;
            }
        }
    }

Odpovědět

21. června 23:05

:D :D :D

DarkCoder

Člen

DarkCoder:22. června 7:51

Časová složitost je stále O(n²).

Skutečný výkon algoritmu může na konkrétním hardwaru ovlivnit práce s pamětí, cache, paralelizace nebo instrukční sada. Algoritmus s horší teoretickou složitostí tak může být v praxi rychlejší, zejména u menších vstupů, a proto se výkon často ověřuje pomocí benchmarkových testů.

Odpovědět

22. června 7:51

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Yveta Kršková

Člen

Yveta Kršková:22. června 12:16

Děkuji ti DarkCodere, myslela jsem si to

Odpovědět

22. června 12:16

:D :D :D

DarkCoder

Člen

DarkCoder:22. června 13:14

Není zač, jinak zde je jednoduší verze.

if (radaCisel.length > 1) {
    for (let i = 0; i < radaCisel.length - 1; i++) {
        let indexMax = i;
        for (let j = i + 1; j < radaCisel.length; j++) {
            if (radaCisel[j] > radaCisel[indexMax]) {
                indexMax = j;
            }
        }
        if (indexMax !== i) {
            let temp = radaCisel[i];
            radaCisel[i] = radaCisel[indexMax];
            radaCisel[indexMax] = temp;
        }
    }
}

Odpovědět

22. června 13:14

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Yveta Kršková

Člen

Yveta Kršková:22. června 13:32

Ano, ta první podmínka slouží k načítání dat zadaných uživatelem, ale stejně je asi v JS správně "undefined" a ne "null", chtěla jsem to pak opravit, ale už to zase nešlo.

Ta druhá vnořená podmínka v cyklu "j" sice nesníží počet operací počítače, ale sníží množství přepisů pole, protože určí rovnou správné maximum, ne až z přepsaného pole na indexu "i".

Ten postup v podstatě "vysvětluje" mou myšlenkovou práci s polem při třídění počítači (takto postupuji myšlenkově já, když něco třídím, vyhledám potřebný prvek ve sbírce prvků, dosadím ho na místo a je mi jedno, kam zpět zahodím ten vyřazený), proto ty české jednoduché názvy, jinak samozřejmě běžně pracuji s angličtinou. Lekce třídění už jsem jinak dojela do konce a vyzkoušet si jiné postupy bylo dost dobré antisklerotické cvičení pro stařešinu na mateřské
Lepší, než koupit si štos křížovek a hlavolamů, řekla bych :'D

Odpovědět

22. června 13:32

:D :D :D

DarkCoder

Člen

DarkCoder:22. června 14:16

Tak to každopádně, vyzkoušet si různá řešení a uvědomit si proč zrovna použít ono před jiným, dá bezesporu hlavě zabrat. Myšlenka je to správná, obvykle se začíná přímo s focusem na konkrétní prvek, ikdyž to povětšinou není ideální řešení. Cest k cíli vede naštěstí více a najít to ideální je to co chceme.

Jinač prvá podmínka vlastně říká: "Má smysl třídit pole?" a to stačí. Není nutné k tomu přidávat něco dalšího.

Pokud se chceš ještě zaobírat myšlenkou výběru a vložením prvku někam, může se ti hodit třeba generátor konkrétních čísel na kterém můžeš pak testovat své algoritmy.

Máš N prvků. Úkol je: Vygeneruj řadu z těchto prvků.
Např. 3 1 8 2 5 a výsledek aby byl např. 5 2 3 8 1 nebo 2 3 5 1 8, apod.
Jak toho docílím? Využij myšlenku ve svém příspěvku.. Není to těžké :-)

Odpovědět

22. června 14:16

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Naučíme tě pracovat na home-office.

Zjistit více...

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 22.

Nejčastěji vyhledáváné

Diskuze – Lekce 1 - Selection sort