Řazení hodnot v poli - Selection Sort (řazení výběrem)
Jedná se o jednoduchý algoritmus, který je vhodný pro malé množství dat. Data jsou rozdělena na seřazenou a neseřazenou část. Ukážeme si dvě varianty algoritmu: řazení výběrem minima a řazení výběrem maxima.
Předpokládáme, že hodnoty jsou uloženy v poli a známe aktuální počet prvků v poli. V uvedených algoritmech řadíme hodnoty vzestupně.
Řazení výběrem minimální hodnoty
Princip algoritmu:
- najdeme prvek s nejmenší hodnotou v neseřazené části posloupnosti
- minimum zaměníme s prvkem na první pozici v neseřazené část
- posuneme hranici seřazené a neseřazené části o 1 pozici vpravo
- opakováním předchozích kroků seřadíme celou posloupnost
Poznámky pro návrh funkce: vstupem do funkce budou hodnoty uložené v poli a aktuální počet hodnot v poli. Naše funkce bude mít 2 parametry (pole, počet). Funkce při seřazení změní uspořádání hodnot v poli, nic víc se funkcí nemění. Musíme tedy změněné pole z funkce vrátit. Protože pole je vstupně-výstupním parametrem funkce, vrací se automaticky. Funkce je bez návratové hodnoty, bude tedy typu void.
void serad_selection_min(float cisla[], int pocet)
{
float pom, min;
int i,imin, zac;
for ( zac = 0; zac < pocet - 1; zac++) //posun zacatku neserazene casti pole
{
min = cisla[zac]; //zacatek algoritmu pro urceni minimalni hodnoty
imin = zac;
for ( i = zac; i < pocet; i++)
{
if ( cisla[i] < min )
{
min = cisla[i];
imin = i;
}
}
pom = cisla[zac]; //zamena prvku s minimalni hodnotou s prvnim prvkem
cisla[zac] = cisla[imin];
cisla[imin] = pom;
}
}
Řazení výběrem maximální hodnoty
Algoritmus je obdobou předchozího - maximum postupně přesouváme na konec neseřazené posloupnosti.
Princip algoritmu:
- najdeme prvek s největší hodnotou v neseřazené části posloupnosti
- maximum zaměníme s prvkem na poslední pozici v neseřazené část
- posuneme hranici seřazené a neseřazené části o 1 pozici vlevo
- opakováním předchozích kroků seřadíme celou posloupnost
void serad_selection_max(float cisla[], int pocet)
{
float cisla[100], pom, max;
int i, pocet, imax, kon;
for ( kon = pocet - 1; kon > 0; kon-- ) //posun konce neserazene casti pole
{
max = cisla[0]; //zacatek algoritmu pro urceni maximalni hodnoty
imax = 0;
for ( i = 0; i < kon + 1; i++)
{
if ( cisla[i] > max )
{
max = cisla[i];
imax = i;
}
}
pom = cisla[kon]; //zamena prvku s maximalni hodnotou s poslednim prvkem
cisla[kon] = cisla[imax];
cisla[imax] = pom;
}
}
Pokuste se upravit oba algoritmy pro sestupné řazení.