Zoradenie 1R poľa
V programovaní sa veľmi často stretávame s potrebou usporiadnania / zoradzovania prvkov. Môže ísť o prvky ako sú čísla, písmena alebo komplexné údajové štruktúry. Existuje množstvo metód a algoritmov. Na tomto predmete si ukážeme najzákladnejší algoritmus bublinkového triedenia a bežne využívaný algoritmus quck sort.
Bublinkové triedenie - bubble sort
Pracuje opakovaným prechodom cez zoznam, ktorý má byť utriedený porovnávajúc vždy dva prvky. Ak prvky nie sú v správnom poradí, zamení ich. Porovnávanie prvkov v zozname trvá, pokiaľ sú potrebné výmeny, teda pokiaľ nie je zoznam usporiadaný. Algoritmus dostal názov vďaka tomu, že menšie prvky sa „prebublinkujú“ na začiatok zoznamu.
| Code Block | ||
|---|---|---|
| ||
void bubble_sort(int numbers[], const int size)
{
for(int j = size-1; j > 0; j--)
for(int i = 0; i < j; i++)
{
if(numbers[i+1] < numbers[i])
{
int tmp = numbers[i+1];
numbers[i+1] = numbers[i];
numbers[i] = tmp;
}
}
} |
Rýchle triedenie - quick sort
Quicksort alebo rýchle triedenie je jeden z najrýchlejších známych triediacich algoritmov založených na porovnávaní prvkov. Jeho priemerná doba výpočtu je najlepšia zo všetkých podobných algoritmov. Algoritmus je aj veľmi jednoduchý. Nevýhodou je, že pri výnimočne nevhodnom tvare vstupných dát môže byť časová a pamäťová náročnosť. Algoritmus vymyslel v roku 1962 Sir Charles Antony Richard Hoare.
Základnou myšlienkou quicksortu je rozdelenie triedenej postupnosti čísel na dve približne rovnaké časti. V jednej časti sú čísla väčšie a v druhej menšie ako istá zvolená hodnota, ktorá sa nazýva pivot. Ak je táto hodnota zvolená dobre, sú obe časti približne rovnako veľké. Ak budú obe časti samostatne roztriedené, je roztriedené i celé pole. Obe časti sa potom rekurzívne triedia rovnakým spôsobom.
Pre použitie funkcie qsort() je potrebné použiť hlavičkový súbor stdlib.h. Tiež je potrebné vytvoriť porovnávaciu funkciu, ktorou qsort bude porovnávať prvky poľa.
| Code Block |
|---|
#include <stdlib.h>
int main()
{
int pole[] = {1, 4, 2, 5, 8, 7, 3, 6};
int pocet=sizeof(pole)/sizeof(int);
qsort(pole, pocet, sizeof(int), porovnaj);
}
int porovnaj(const void* var1, const void* var2)
{
return *(int*)var1 - *(int*)var2;
}
|
Vyhľadávanie v 1R poliach
Rovnako ako pre zoradenie aj pre vyhľadávanie existuje mnoho algoritmov. Najzákladnejším je lineárne vyhľadávanie a pokročilejším zasa binárne vyhľadávanie.