Wikipedie

Řazení výběrem: Porovnání verzí

Interaktivně procházet historii
← Přejít na předchozí porovnáníPřejít na další porovnání →
Smazaný obsah Přidaný obsah
VizuálníWikitext
Opraven odkaz C#
dva naprosto stejné programovací jazyky jako ten předchozí (z toho jeden byl špatně a nešel ani přeložit) vyhozeny; příklad na stabilitu opraven na takový, který se tak opravdu chová, a doplněna poznámka o alternativní implementaci
Řádek 1:
[[FileSoubor:Selection sort animation.gif|thumb|Ilustrace řazení výběrem na náhodné množině]]
[[ImageSoubor:Selection-Sort-Animation.gif|right|thumb|Animace selection sortu. Červeně je zvýrazněno aktuální minimum. Žlutě je označena srovnaná část seznamu. Modrá je aktuální položka]]
'''Řazení výběrem''' ({{Vjazyce|en}} {{Cizojazyčně|en|'''selection sort'''}}) je implementačně jednoduchý [[Algoritmus řazení|řadicí algoritmus]] s časovou složitostí {{math|[[asymptotická složitost|''O'']](<var>N</var>²)}}. Pro svou jednoduchou [[implementace|implementaci]] a nízký [[overhead]] bývá často používán pro uspořádávání malých množství dat. Pro větší objem dat se používají algoritmy s nižší časovou složitostí {{math|''O''(<var>N</var> log <var>N</var>)}} jako [[Heapsort]] nebo [[Merge sort|Mergesort]].
 
Řádek 17:
Algoritmus není [[Stabilní řazení|stabilním]] (může změnit pořadí u prvků se shodným klíčem).
 
Je to dáno tím, že se prohazují nesousední prvky. Například pokud uvážíme [[Množina|množinu]] <math>M = \{5, 3_1, 12, 3_2, 21\}</math>, tak nám ji algoritmus seřadí jako <math>M = \{1, 2, 3_2, 3_1, 5\}</math>. Zde je jasně vidět, že algoritmus prohodil prvky <math>\{3_1\}</math> a <math>\{3_2\}</math>, což stabilní algoritmus řazení neudělá.
 
Řazení výběrem je možno implementovat i stabilně, pokud se místo záměny prvků použije přesunutí nalezeného nejmenšího prvku na příslušné místo, k tomu je ovšem potřeba použití datové struktury s rychlým vkládáním a odstraňováním, například [[spojový seznam]], jinak výrazně zhorší výkonnost algoritmu.
== Implementace algoritmu v jazyce [[C (programovací jazyk)|C]] ==▼
 
== Implementace algoritmu v jazyce [[C Sharp|C#]] ==▼
▲== Implementace algoritmuPříklad v jazyce [[C (programovací jazyk)|C]] ==:
<source lang="c">
void selectionSort(int data[], int count)
Řádek 28 ⟶ 31:
mi = i;
for (j = i+1; j < count; j++) {
if (data[j] < data[mi]) {
mi = j;
}
}
/* vyměníme data[i] a data[mi] */
Řádek 38 ⟶ 41:
}
}
</source>
== Implementace algoritmu v jazyce [[Java (programovací jazyk)|Java]] ==
<source lang="java">
public static void selectionSort1(int[] x) {
for (int i=0; i<x.length-1; i++) {
for (int j=i+1; j<x.length; j++) {
if (x[i] > x[j]) {
int index = j;
}
}
// vyměníme x[i] a x[index]
int temp = x[i];
x[i] = x[index];
x[index] = temp;
}
}
</source>
▲== Implementace algoritmu v jazyce [[C Sharp|C#]] ==
<source lang="csharp">
public static int[] SelectionSort(int[] pole)
{
int i = pole.Length;
int i2 = 0;
int min, help;
while (i != 0)
{
i--;
min = i;
while (i2 != i)
{
if (pole[min] <= pole[i2])
{
min = i2;
}
i2++;
}
i2 = 0;
help = pole[i];
pole[i] = pole[min];
pole[min] = help;
 
}
 
return pole;
}
</source>
 
Citováno z „https://cs.wikipedia.org/wiki/Řazení_výběrem“