Fotografický magazín "iZIN IDIF" každý týden ve Vašem e-mailu.
Co nového ve světě fotografie!
Zadejte Vaši e-mailovou adresu:
Kamarád fotí rád?
Přihlas ho k odběru fotomagazínu!
Zadejte e-mailovou adresu kamaráda:
C/C++
Řadící algoritmy v C++
14. února 2002, 00.00 | Dnes se podiváme na řadící algoritmy v C++. V STL existují již hotové šablony. Podíváme se také, jaké jsou možnosti řadit v jayzce C. Řadící algoritmy slouží k seřazení pole, nebo kontejneru. Někdy jsou řadící algoritmy nepřesně nazývány třídicí.
Řadící algoritmy jsou algoritmy, které seřadí prvky v kontejneru, nebo jeho části. Řadícím algoritmům se často říká třídicí algoritmy. Není to ale přesné označení, protože pod pojmem třídicí algoritmus by jsme si měli představit spíše něco, co rozděluje objekty podle toho, jaké jsou třídy. Prvky lze seřadit podle nějaké relace. Algoritmy z STL k řazení používají buď operátor <, který může být implicitní, nebo přetížený. Dále také umožňují programátorovi zadat funkci vracející bool, která definuje relaci, podle níž mají být prvky seřazeny.
Řazení v CJeště než se začneme věnovat řadícím šablonám z STL chtěl bych připomenout, že existuje možnost standardního řazení i v ANSI C (nejenom v C++). Jazyk C nezná šablony. K řazení je v C k dispozici funkce qsort deklarovaná v hlavičkovém souboru stdlib.h. Její deklarace je: void qsort(void *pole, size_t pocet, size_t velikost, int (*porovnani)(const void *prvni, const void *druhy));. Prvním parametrem je ukazatel na pole, které chceme seřadit. Jedná se vlastně o ukazatel na první prvek pole (prvek s indexem 0). Druhým parametrem je počet prvků, které chceme seřadit. Následuje velikost jednoho prvku a ukazatel na porovnávací funkci. Mluvíme o jazyku C, nikoliv C++, proto žádné přetěžování operátoru < není možné. Ukazatel na funkci ukazuje na funkci vracející int mající dva parametry, což jsou ukazatele na void. Tato funkce by měla vracet libovolné záporné číslo, je-li *a < *b, měla by vracet 0, jestliže *a == *b, a vracet libovolné kladné číslo, jestliže *a > *b. Tím, že zadáváme porovnávací funkci, i velikost prvku, je funkce qsort univerzální. Je použitelná pro pole jakýchkoliv prvků. Uvedeme si příklad. Nejprve seřadíme pole int, potom pole bodů v 2D podle jejich vzdálenosti k bodu 0,0. Úmyslně program napíši v ANSI C, nepoužiji nic z ANSI C++.
|
Tolik k funkci qsort z jazyka C. Uvedl jsem ji, protože se na ni často zapomíná.
Řazení v C++Jazyk C++ po C "zdědil" funkci qsort. Můžeme ji tedy používat i v C++. Já to ale nedoporučuji. Funkce qsort umí uspořádat pouze pole. Neuspořádáme s ní žádný kontejner z STL. V C++ máme k dispozici šablony funkcí, které umí uspořádat i pole, i datové kontejnery. Než se jim budeme věnovat, podívejme se na trochu teorie o "stabilním" řazení.
Stabilní řazení je řazení, které garantuje, že prvky, které mají stejný klíč (podle kterého se prvky řadí) vůči sobě nezmění pořadí. U "nestabilního" řazení může být tato vlastnost také splněna, ale nemáme jistotu, že tomu tak bude vždy.
K řazení v C++ existují algoritmy sort a stable_sort. Deklarace:
- template <class RandomAccessIterator> void sort (RandomAccessIterator zacatek, RandomAccessIterator konec); - Seřadí oblast danou iterátory začátek a konec podle operátoru <. Operátor < může být implicitní, nebo přetížený. Parametrem šablony je typ iterátoru, parametry funkce jsou iterátory udávající oblast pro seřazení.
- template <class RandomAccessIterator, class TPorovnani> void sort (RandomAccessIterator zacatek, RandomAccessIterator konec, TPorovnani porovnani); - Stejná činnost jako u předchozího algoritmu. Rozdíl je jen v tom, že k porovnání dvou prvků nebude použit operátor <, ale funkce, nebo funkční objekt zadaný programátorem. TPorovnani je buď třída funkčních objektů, nebo ukazatel na funkci. Musí mít dva parametry stejného typu (prvky), a vracet typ bool, případně celé číslo.
- template <class RandomAccessIterator> void stable_sort (RandomAccessIterator zacatek, RandomAccessIterator konec); - Význam parametrů je stejný jako u algoritmu sort. Rozdíl je jen v tom, že stable_sort řadí stabilně.
- template <class RandomAccessIterator, class TPorovnani> void stable_sort (RandomAccessIterator zacatek, RandomAccessIterator konec, TPorovnani porovnani); - Význam parametrů je stejný jako u algoritmu sort. Rozdíl je jen v tom, že stable_sort řadí stabilně.
Ukážeme si vše v příkladu.
|
Příště se podíváme haldu, povíme si co to je, a ukážeme si standadní operace nad haldou, které nám C++ poskytuje.
Obsah seriálu (více o seriálu):
- Základy OOP v C++: Od C k C++
- Základní pojmy objektově orientovaného programování
- Vytváření tříd, instance třídy, zasílání zpráv v C++
- Vytváření instancí - konstruktory, destruktory
- Kopírovací konstruktor v C++
- Jednoduchá dědičnost v C++
- Časná versus pozdní vazba - úvod do polymorfismu v C++
- Polymorfismus - dokončení
- Vícenásobná dědičnost v C++
- Vícenásobná dědičnost v C++ - opakovaná dědičnost
- Vícenásobná dědičnost v C++ - volání konstruktorů a destruktorů
- Přetěžování operátorů v C++ 1.díl
- Přetěžování operátorů v C++ 2. díl
- Vstupní a výstupní operace pomocí datových proudů v C++
- Přetěžování operátorů << a >> pro datové proudy v C++
- Neformátovaný vstup a výstup v C++
- Paměťové proudy v C++
- Prostory jmen v C++
- Řetězce v C++
- Výjimky v C++
- Výjimky v C++ - výjimky tvoří dědičnou hierarchii
- Výjimky v C++ - dokončení
- Dynamická identifikace typů v C++
- Přetypování v C++
- Problémy s typy při vícenásobné dědičnosti
- Šablony funkcí v C++
- Šablony datových typů v C++
- Vnitřní typy u parametrů šablon, vnořené šablony v C++
- Pole s libovolným intervalem indexování v C++
- Datové kontejnery v C++ - Úvod do STL
- Vector - datový kontejner v C++
- Iterátory v C++
- Šablona vector v C++ a iterátory
- Asociativní pole v C++
- Množina v C++
- Funkční objekty v C++
- Standardní funkční objekty v C++
- Úvod do standardních algoritmů v C++
- Kopírovací a přesouvací algoritmy v C++
- Vyhledávací algoritmy v C++
- Skenovací (prohlížecí) algoritmy v C++
- Transformační algoritmy v C++
- Řadící algoritmy v C++
- Halda v C++
- Standardní algoritmy v C++ - dokončení
- Automatické ukazatele v C++
- Inteligentní ukazatel - čítač referencí v C++
- Použití čítače referencí v C++
- Kopírování velkých objektů v C++
- Řízené kopírování prvků v poli v C++
- Dokončení seriálu objektově orientované programování v C++
Diskuse k článku
-
25. listopadu 2012
-
30. srpna 2002
-
10. října 2002
-
4. listopadu 2002
-
12. září 2002
-
25. listopadu 2012
-
28. července 1998
-
31. července 1998
-
28. srpna 1998
-
6. prosince 2000
-
27. prosince 2007
-
4. května 2007