Lekce 1 - Selection sort

Další

Selection sort je jedním z nejjednodušších řadících algoritmů. Jeho myšlenka spočívá v nalezení minima, které se přesune na začátek pole (nebo můžeme hledat i maximum a to dávat na konec). V prvním kroku tedy nalezneme nejmenší prvek v poli a ten poté přesuneme na začátek. V druhém kroku již nebudeme při hledání minima brát v potaz dříve nalezené minimum. Po dostatečném počtu kroků dostaneme pole seřazené. Algoritmus má nepříliš výhodnou časovou složitost a není stabilní. Je však velice jednoduchý na pochopení i implementaci.

Vlastnosti algoritmu

Časová složitost	(n²)
Stabilita	Ne
Rychlost	Pomalý

Pozn. je myšlena časová složitost průměrného případu a rychlost vzhledem ke všem třídícím algoritmům.

Průběh

Máme pole následujících prvků:

Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!

Nyní cyklem projedeme pole od prvního do posledního prvku (rozsah cyklu je zvýrazněn barevně) a vybereme to nejmenší číslo (zde 1).

Toto číslo prohodíme s prvním číslem (zde s 3):

Tímto krokem jsme dostali první prvek v pole zatříděný. Nyní cyklem opět projedeme pole a najdeme nejmenší prvek. Ale protože ten úplně nejmenší již máme na začátku, nebudeme ho zahrnovat a projedeme tedy pole od druhého do posledního prvku a opět vybereme nejmenší prvek (2):

Prvek si opět zatřídíme, protože již máme 1 prvek zatříděný z minula, prohodíme ho s druhým prvkem (5).

Teď máme již 2 první prvky správně. Takto budeme pokračovat dále, budeme vybírat minimum ze zbylých prvků a zatřizovat ho tak dlouho, dokud nebudeme mít pole celé setříděné. Další kroky algoritmu by vypadaly následovně:

Poslední prvek je již logicky zatříděný, proto si můžeme tento krok ušetřit. A je hotovo.

Vizualizace

Video ukázka

Zdrojový kód

public static void selectionSort(int[] list) {
  int temp, min;
  for (int i = 0; i < (list.length - 1); i++) {
    min = list.length - 1;
    // hledani minima
    for (int j = i; j < (list.length - 1); j++)
      if (list[min] > list[j])
        min = j;
    // prohozeni prvku
    temp = list[min];
    list[min] = list[i];
    list[i] = temp;
  }
}

public static void selectionSort(int[] list) {
  int temp, min;
  for (int i = 0; i < (list.Length - 1); i++) {
    min = list.Length - 1;
    // hledani minima
    for (int j = i; j < (list.Length - 1); j++)
      if (list[min] > list[j])
        min = j;
    // prohozeni prvku
    temp = list[min];
    list[min] = list[i];
    list[i] = temp;
  }
}

{PHP}
function selection_sort(array &$list) {
  for ($i = 0; $i < (count($list) - 1); $i++) {
    $min = count($list) - 1;
    // hledani minima
    for ($j = $i; $j < (count($list) - 1); $j++)
      if ($list[$min] > $list[$j])
        $min = $j;
    // prohozeni prvku
    $temp = $list[$min];
    $list[$min] = $list[$i];
    $list[$i] = $temp;
  }
}


$list = [3, 5, 2, 8, 9, 1];
selection_sort($list);
print_r($list);

{/PHP}

V další lekci, Bubblesort, si ukážeme algoritmus Bubblesort i se zdrojovými kódy.

Článek pro vás napsal David Čápka

Uživatelské hodnocení:

50 hlasů

David je zakladatelem ITnetwork a programování se profesionálně věnuje 13 let. Má rád Nirvanu, sushi a svobodu podnikání.

David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.

Aktivity

Komentáře

Don

Člen

Don:25.9.2011 16:21

Trochu nechápu větu "Nyní cyklem projedeme pole od prvního do posledního prvku (rozsah cyklu je zvýrazněn barevně) a vybereme to nejmenší číslo (zde 9)." Píše se zde že vybereme nejmenší číslo ale v závorce je číslo 9 a v tabulce pracujeme s číslem 1. Myslím že v závorce mělo být napsané číslo 1.

Odpovědět

25.9.2011 16:21

David Čápka

Tým ITnetwork

Odpovídá na Don
David Čápka:25.9.2011 22:03

V původní verzi článku jsem třídil pomocí hledání maxima, zapomněl jsem to změnit, díky za upozornění

Odpovědět

25.9.2011 22:03

One of the most common causes of failure is the habit of quitting when one is overtaken by temporary defeat.

martinkobelka

Tvůrce

martinkobelka:28.7.2012 13:20

kod pro php

$pole = array(1,8,7,4,2);
for($i=0;$i<count($pole);$i++){
    for($j=$i;$j<count($pole);$j++){
        if($i == $j){
            $min = $pole[$j];
            $cislop = $j;
        }
        else{
            if($pole[$j] < $min){
                $min = $pole[$j];
                $cislop = $j;
            }
        }
    }
    $mezi = $pole[$i];
    $pole[$i] = $min;
    $pole[$cislop] = $mezi;
}

echo implode($pole, ", ");

Odpovědět

28.7.2012 13:20

jahoda.l

Člen

Odpovídá na martinkobelka
jahoda.l:16.4.2013 15:23

Osobně bych to řešil v PHP spíše nějak takto:

function selection_sort(array $sortedArray){
  $lenght = count($sortedArray);
  $temp = null;
  for($actualPossition = 0; $actualPossition < $lenght; ++$actualPossition){
      $min = null;
      for($runPossiton = $actualPossition; $runPossiton < $lenght; ++$runPossiton){
        if($sortedArray[$runPossiton] < $min || $min === null){
          $min = $sortedArray[$runPossiton];
          $temp = $runPossiton;
        }
      }
      $sortedArray[$temp] = $sortedArray[$actualPossition];
      $sortedArray[$actualPossition] = $min;
  }
  return $sortedArray;
}

Dle výkonu je v PHP dobré nepoužívat funkce jako např. "count" při cyklech, jelikož při každém průchodu cyklu se funkce znovu volá. Je tedy výhodnější jí uložit do proměnné.

Další ačkoliv zvláštní performance je používání ++$i namísto $i++ jedná se sice o cca 13% ovšem ale při algorytmu by jsme měli řešit i 13%.

Přikládám ještě odkaz na benchmark: http://www.phpbench.com/

Odpovědět

16.4.2013 15:23

Michal

Člen

Michal:4.5.2014 10:55

C++

template<typename T>
void selectionSort(std::vector<T>& vect)
{
   for (unsigned i = 0, j = 0; i < vect.size() - 1; ++i)
   {
      T min = vect[vect.size() - 1];
      // Hledání minima.
      for (j = i; j < vect.size() - 1; ++j)
         if (vect[j] < min)
            min = vect[j];
      // Prohození.
      std::swap(vect[i], vect[j]);
   }
}

Editováno 4.5.2014 10:57

Odpovědět

4.5.2014 10:55

Don’t worry if it doesn’t work right. If everything did, you’d be out of a job.

Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!

Maxfx

Tvůrce

Maxfx:2.7.2014 20:12

void selectionSort(int f[], int size)
{
        int min = 0;

        for(int i = 0; i < size; i++)
        {
                min = i;

                for(int j = i + 1; j < size; j++)
                {
                        if(f[min] > f[j]) min = j;
                }

                swap(f[i], f[min]);
        }
}

Odpovědět

2.7.2014 20:12

Být ovládán znamená být sledován, pod dohledem, špehován, veden, uzákoněn, reglementován, ohrazen, indoktrinován, pře...

Neaktivní uživatel

Tvůrce

Neaktivní uživatel:10.1.2017 17:27

Optimalizovaný kód pre PHP:

function selectionDesc(array $input) {

    $arrayLength = sizeof($input);
    $key = null;

    $i = 0;
    while($i < $arrayLength) {

        $key = $i;
        $min = $input[$i];

        $j = $i + 1;
        while($j < $arrayLength) {

            if($input[$j] > $min) {
                $key = $j;
                $min = $input[$j];
            }

            ++$j;

        }

        $input[$key] = $input[$i];
        $input[$i] = $min;
        ++$i;

    }

    return $input;

}

Pre opačné usporiadanie stačí otočiť porovnávanie v podmienke.

Odpovědět

10.1.2017 17:27

Neaktivní uživatelský účet

Rostislav Kuruc

Brigádník

Rostislav Kuruc:23.10.2020 10:17

Kod pro Python

def selectionSort(array):
# O(n^2)
    for i in range(len(array)):

        min_index = i
        # prochazime cele pole

        for j in range(i+1, len(array)):
            # projedeme zbyvajici prvky pole (protoze i+1)
            if(array[min_index] > array[j]):
                # nalezli jsme nejmensi prvek, tak si ulozime jeho index
                min_index = j

        # prohodime prvek z prvniho iteracniho cyklu s nejmensim nalezenym
        array[i], array[min_index] = array[min_index], array[i]

    return array

Odpovědět

23.10.2020 10:17

Matematika je programovacim jazykem vesmiru...

Lenka Polláková

Člen

Odpovídá na Don
Lenka Polláková:28.11.2021 2:53

To je tak no,jednoduchosť sa ťažko chápe. Rozumiem

Odpovědět

28.11.2021 2:53

Eva Šimerková

Člen

Eva Šimerková:8. ledna 10:20

Ahoj, moc jsem nepochopila, jak mám funkci vložit do svého programu.
Učím se programovat v C# a nevím, jestli mám nahradit to "static void Main(string[] args)" tím "public static int[] selectionSort(int[] pole)" a jestli mám to pole určit předtím nebo potom. Bude potom program fungovat? Nebo tam musím zadat ještě něco?

Odpovědět

8. ledna 10:20

Tisíce ajťáků chybí, platy stoupají. Staň se hrdinou!

Zjistit více...

Zachránit situaci

Kritická situace!

Tisíce ajťáků chybí, platy stoupají. Staň se hrdinou!

Zachránit situaci

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 10.