Úvod do triedenia v C ++
Ak má súbor prvkov na objednávku, triedenie pomáha pri usporiadaní prvkov v zázname na základe poradia vzťahov. Zoberme si záznam súboru, ktorý obsahuje veľa informácií, na prístup k zoznamu zo záznamu je potrebné mať kľúčové pole, ktoré nasmeruje aktuálne umiestnenie prvku. Napríklad, zvážte zoznam mien v databáze, mohol by byť usporiadaný podľa abecedy. Triedenie dalo dôležitú úlohu v oblasti počítačov a technológií. Uvidíme viac v tomto článku.
Čo je triedenie v C ++?
Triedenie je základný koncept používaný programátorom alebo výskumníkom na triedenie požadovaných vstupov. Poradie zložitosti je dané 0 (N * log (N)). Triedenie vstupu uľahčuje riešenie mnohých problémov, ako je napríklad vyhľadávanie, maximum a minimum. Aj keď triedenie usporiada údaje v poradí, účinnosť procesu je veľmi dôležitá, ktorá je založená na dvoch kritériách: - Čas a pamäť, ktoré sú potrebné na vykonanie triedenia na daných údajoch. Čas sa meria počítaním porovnaní použitých klávesov. Existuje rad algoritmov, ktoré je možné usporiadať. Triedenie v C ++ sa vo všeobecnosti rozlišuje na dva typy:
- Vnútorné triedenie
- Externé triedenie
Syntax a príklad
syntaxe:
C ++ používa vstavané funkcie sort () pre svoje algoritmy na triedenie kontajnerov, ako sú vektory, polia.
Zoradiť (pole, pole + veľkosť);
Príklady:
#include
using namespace std;
int main ()
(
int ins(12) = ( 19, 13, 5, 27, 1, 26, 31, 16, 2, 9, 11, 21);
cout<<"\nInput list is \n";
for(int i=0;i<12;i++)
(
cout < )
for(int k=1; k<12; k++)
(
int t = ins(k);
int j= k-1;
while(j>=0 && t <= ins(j))
(
ins(j+1) = ins(j);
j = j-1;
)
ins(j+1) = t;
)
cout<<"\nSorted list is \n";
for(int i=0;i<12;i++)
(
cout < )
)#include
using namespace std;
int main ()
(
int ins(12) = ( 19, 13, 5, 27, 1, 26, 31, 16, 2, 9, 11, 21);
cout<<"\nInput list is \n";
for(int i=0;i<12;i++)
(
cout < )
for(int k=1; k<12; k++)
(
int t = ins(k);
int j= k-1;
while(j>=0 && t <= ins(j))
(
ins(j+1) = ins(j);
j = j-1;
)
ins(j+1) = t;
)
cout<<"\nSorted list is \n";
for(int i=0;i<12;i++)
(
cout < )
)#include
using namespace std;
int main ()
(
int ins(12) = ( 19, 13, 5, 27, 1, 26, 31, 16, 2, 9, 11, 21);
cout<<"\nInput list is \n";
for(int i=0;i<12;i++)
(
cout < )
for(int k=1; k<12; k++)
(
int t = ins(k);
int j= k-1;
while(j>=0 && t <= ins(j))
(
ins(j+1) = ins(j);
j = j-1;
)
ins(j+1) = t;
)
cout<<"\nSorted list is \n";
for(int i=0;i<12;i++)
(
cout < )
)
Výkon:
Ako to funguje?
Najprv si preberieme Quick Sort, čo sa považuje za dôležitú metódu medzi rôznymi typmi triedenia. Základné triedenie poľa vyžaduje prístup Quicksort. Existujú rôzne spôsoby, ako implementovať triedenie. Cieľ každej z týchto techník je rovnaký ako porovnanie dvoch prvkov a ich výmena s dočasnou premennou. V tomto článku sa budeme venovať najdôležitejšiemu triedeniu použitému pri implementácii. Toto sú:
- Triedenie bubliniek
- Zoradenie vloženia
- Rýchle zoradenie
- Výber Zoradiť
Existuje triedenie zlúčenia, radix triedenie, triedenie pások, o ktorom sa budeme baviť neskôr. Najprv pôjdeme s Bubble sort.
1. Zoradenie bubliniek
Bublinové triedenie je jednou z najjednoduchších metód triedenia, ktorú môžeme použiť pre aplikácie. Pri tejto technike sa postupné swapy vytvárajú prostredníctvom záznamov, ktoré sa majú triediť. V každom kroku porovnáva kľúč s údajmi a vymieňa si prvky, ak nie v požadovanom poradí. Zoradenie sa vykonáva so susednými prvkami v tom čase, keď sa po výmene umiestni na miesto triedenia iba jeden prvok.
Príklad: Uvažujme netriedené pole A () = (6, 2, 4, 7, 1)
| 6 | 2 | 4 | 7 | 1 |
| A (0) | A (1) | A (2) | A (3) | A (4) |
Krok 1: Ak porovnáme A (0)> A (1), ak je splnená podmienka, vymeňte prvok (6> 2) za true, umiestnite 2 do A (0). Podobne všetky kroky prebiehajú rovnako, kým sa pole nezoradí.
Teraz je pole A () = (2, 6, 4, 7, 1)
Krok 2: 6 je porovnávaný so 4. Pretože 6 je väčší ako 4. Preto sa 6 a 4 zamieňajú.
Teraz je pole A () = (2, 4, 6, 7, 1)
Krok 3: Prvok 6 je porovnávaný so 7. Pretože 6 <2 a prvky sú vzostupne, prvky sa nevymieňajú.
Zoradené pole je A () = (2, 4, 6, 7, 1).
Pokračujte v procese, kým sa pole nezoradí.
2. Zoradenie vloženia
V tejto technike začíname s druhým dátovým prvkom za predpokladu, že prvý prvok je už usporiadaný a porovnanie sa uskutoční s druhým prvkom a krok pokračuje s ďalším nasledujúcim prvkom. V rade prvkov N je potrebné mať prechody N-1, aby mal triedený prvok.
Zvážte pole A () = (8, 3, 6, 1)
| 8 | 3 | 6 | 1 |
Krok 1: Prvý prvok hľadá najväčší prvok v poli na výmenu. Ak je väčšia, zostáva rovnaká a presunie sa k druhému prvku, tu 8 je väčšie ako všetky, nedochádza k žiadnemu vymeneniu.
| 8 | 3 | 6 | 1 |
Krok 2: Výmena s druhým prvkom
| 3 | 8 | 6 | 1 |
Krok 3: Výmena s tretím prvkom
| 3 | 6 | 8 | 1 |
Krok 4: Výmena so štvrtým prvkom
| 1 | 3 | 6 | 8 |
3. Rýchle zoradenie
Táto technika sa riadi algoritmom delenia a dobývania a považuje sa za veľmi efektívnu a rýchlejšiu pre veľké polia. Sú rozdelené do troch podsekcií: ľavá, pravá a stredná. Prostredný prvok má jednu hodnotu a nazýva sa pivot. Mechanizmus vyzerá takto, prvok v ľavom segmente by nemal mať kľúč väčší ako stredný prvok a žiadny prvok napravo nemá kľúč, ktorý je menší ako kľúč stredného prvku. Teraz začnime s ilustráciou procesu triedenia. Pri triedení čiastkových častí používa Quicksort rekurzívny koncept. Pole je rozdelené do podčasti, opäť ľavý a pravý segment sú rozdelené dobývaním. Tu má v tomto príklade vzhľadom na to, že posledný prvok má čap a prvý prvok sa považuje za nízky. Zvážte prvok poľa
| 49 | 22 | 11 | 16 | 56 | 30 |
Prevzatie prvku úplne vpravo má otočný prvok = 30
| 16 | 22 | 11 | 30 | 56 | 49 |
Prvok väčší ako čap je umiestnený smerom doľava, menší vpravo.
| 16 | 22 | 11 | 56 | 49 |
Ukazovateľ je umiestnený na čape a je rozdelený okolo čapu.
| 11 | 22 | 16 | 56 | 49 |
Časti sú usporiadané jednotlivo.
| 11 | 16 | 22 | 30 | 49 | 56 |
Nakoniec sme dostali zoradené pole.
4. Výber zoradenia
Táto technika sa tiež nazýva výmenné triedenie, vykonáva dvojité vyhľadávanie a triedenie operácií. Implementácia si vyžaduje priame triedenie podľa definície uvedenej nižšie. Tu je potrebné identifikovať najmenší prvok prítomný v poli a tento prvok je usporiadaný v prvej i-tej polohe. Ďalej je identifikovaný druhý najmenší prvok a je usporiadaný v druhej polohe. Keď sa netriedený podčasť vyprázdni, výberový typ opustí svoju slučku. Časová zložitosť je daná ako O (n2).
Zvážte nasledujúce pole:
| 63 | 26 | 13 | 23 | 12 |
1. Nájdite najmenší prvok a umiestnite ho na začiatok a zamení sa za polohu.
| 12 | 26 | 13 | 23 | 63 |
2. Druhý prvok a (1) je označený v porovnaní s minimálnym prvkom a umiestni ho do druhej polohy, podobne pokračuje priechod.
| 12 | 13 | 26 | 23 | 64 |
Konečný triedený výstup
| 12 | 13 | 23 | 26 | 64 |
záver
Na záver, tento článok sa zameriaval na koncepty triedenia a ich pracovný mechanizmus. Všetky tieto techniky triedenia používajú koncepty paralelného spracovania. Triedenie tvorí hlavný stavebný blok v štruktúrovacích algoritmoch na riešenie problémov s údajmi v reálnom svete triedením sady hodnôt podľa požiadaviek.
Odporúčané články
Toto je sprievodca triedením v C ++. Tu diskutujeme úvod a syntax s príkladmi spolu s tým, ako to funguje. Viac informácií nájdete aj v ďalších navrhovaných článkoch -
- Triedenie v Tableau
- Iterátor v C ++
- Funkcie poľa v C
- Halda Zoradiť podľa C.
- Ako sa triedenie vykonáva v PHP?
- Halda Zoradiť v Pythone
- Iterátor v Jave
- Prvých 11 funkcií a výhod C ++
- Iterátor v Pythone Výhody a príklady Pythonu