Introducere privind sortarea în C ++
Având o colecție de elemente pentru a comanda, sortarea ajută la aranjarea elementelor din înregistrare pe baza relației de comandă. Luați în considerare o înregistrare de fișiere care conține o mulțime de informații, pentru a accesa o listă din înregistrare este necesar să aveți un câmp cheie pentru a indica locația curentă a elementului. De exemplu, luați în considerare o listă de nume din baza de date, aceasta ar putea fi sortată alfabetic. Sortarea a jucat un rol important în domeniul calculatoarelor și tehnologiei. Să vedem mai multe în acest articol.
Ce este Sortarea în C ++?
Sortarea este conceptul de bază folosit de programator sau de cercetător pentru a sorta intrările necesare. Ordinea complexității este dată de 0 (N * log (N)). Sortarea unei intrări simplifică rezolvarea multor probleme cum ar fi Căutarea, elementul maxim și minim. Deși o sortare aranjează date în secvență, eficiența procesului este foarte importantă, care se bazează pe două criterii: - Timp și memorie necesară pentru a efectua sortarea datelor date. Timpul se măsoară prin numărarea comparațiilor tastelor utilizate. Există mulți algoritmi disponibili pentru a sorta. În general, Sortarea în C ++ se distinge în două tipuri:
- Sortare internă
- Sortare externă
Sintaxă și exemplu
Sintaxă:
C ++ folosește funcția () încorporată pentru algoritmii lor, pentru a sorta containerele precum vectori, tablouri.
Sortare (tablou, tablou + dimensiune);
Exemple:
#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 < )
)
ieşire:
Cum functioneazã?
Pentru început, vom lua Sortarea rapidă, care este considerată o metodă importantă printre diferite tipuri de sortare. Sortarea de bază a unui tablou are o abordare Quicksort. Există moduri diferite de implementare a sortării, scopul fiecăreia dintre aceste tehnici este același cu compararea a două elemente și schimbarea acestora cu variabila temporară. În acest articol, vom discuta despre cele mai importante sortări utilizate pentru implementare. Următoarele sunt:
- Sort de bule
- Sortare inserție
- Sortare rapida
- Sortare selecție
Există sortare Merge, sortare radix, sortare bandă despre care vom putea discuta mai târziu. În primul rând, vom merge cu Bubble sort.
1. Sortare cu bule
Sortarea cu bule este una dintre cele mai simple metode de sortare pe care le putem folosi pentru aplicații. În această tehnică, se fac schimburi succesive prin înregistrările care urmează să fie sortate. La fiecare etapă, se compară cheia datelor și se schimbă elementele, dacă nu în ordinea dorită. Sortarea se face cu elementele adiacente în momentul în care un singur element este plasat în locul sortat după o schimbare.
Exemplu: Să luăm în considerare un tablou nesortat A () = (6, 2, 4, 7, 1)
| 6 | 2 | 4 | 7 | 1 |
| A (0) | A (1) | A (2) | A (3) | A (4) |
Pasul 1: Compararea A (0)> A (1), dacă condiția este adevărată schimbă elementul (6> 2) adevărat, așezați 2 în A (0). În mod similar, toți pașii durează la fel până când tabloul devine sortat.
Acum, tabloul este A () = (2, 6, 4, 7, 1)
Pasul 2: 6 este comparat cu 4. Cum 6 este mai mare decât 4. Prin urmare, 6 și 4 sunt schimbate.
Acum, tabloul este A () = (2, 4, 6, 7, 1)
Pasul 3: Elementul 6 este comparat cu 7. Din moment ce 6 <2 și elementele sunt în ordine crescătoare, elementele nu sunt schimbate.
Matricea sortată este A () = (2, 4, 6, 7, 1).
Continuați procesul până la sortarea tabloului.
2. Sortare inserție
În această tehnică începem cu cel de-al doilea element de date, presupunând că primul element este deja sortat și comparația se face cu cel de-al doilea element, iar pasul este continuat cu celălalt element ulterior. Într-o serie de N elemente, este necesar să aveți N-1 pase pentru a avea un element sortat.
Luați în considerare un tablou A () = (8, 3, 6, 1)
| 8 | 3 | 6 | 1 |
Pasul 1: Primul element caută schimbarea celui mai mare element din tablou. Dacă este mai mare, rămâne același și trece la al doilea element, aici 8 este mai mare decât toate, nu se face schimb.
| 8 | 3 | 6 | 1 |
Pasul 2: Schimbarea cu al doilea element
| 3 | 8 | 6 | 1 |
Pasul 3: Schimbarea cu cel de-al treilea element
| 3 | 6 | 8 | 1 |
Pasul 4: Schimbarea cu al patrulea element
| 1 | 3 | 6 | 8 |
3. Sortare rapidă
Această tehnică urmărește algoritmul de împărțire și cucerire și considerată a fi foarte eficientă, precum și mai rapidă pentru tablele uriașe. Ele sunt împărțite în trei subsecțiuni: stânga, dreapta și mijloc. Elementul de mijloc are o singură valoare și este denumit pivot. Mecanismul merge astfel, elementul din segmentul din stânga nu trebuie să aibă o cheie mai mare decât elementul din mijloc și niciun element din dreapta nu are o cheie mai mică decât cea a elementului din mijloc. Acum să începem cu o ilustrare a procesului de sortare. Quicksort folosește un concept recursiv în timp ce sortează sub-partea. Matricea este împărțită în subparti, iar segmentele din stânga și din dreapta sunt partiționate prin cucerire. Aici, în acest exemplu, considerând că ultimul element are pivot și primul element este presupus scăzut. Luați în considerare un element de matrice
| 49 | 22 | 11 | 16 | 56 | 30 |
Luând elementul cel mai bun are elementul pivot = 30
| 16 | 22 | 11 | 30 | 56 | 49 |
Elementul mai mare decât pivotul este plasat spre stânga, mai mic la dreapta.
| 16 | 22 | 11 | 56 | 49 |
Indicatorul este plasat la pivot și este împărțit în jurul unui pivot.
| 11 | 22 | 16 | 56 | 49 |
Subpartile sunt sortate individual.
| 11 | 16 | 22 | 30 | 49 | 56 |
În cele din urmă, am obținut un Array Sortat.
4. Sortare selecție
Această tehnică se mai numește și sortarea schimbului efectuează căutarea și sortarea dublă a operației. Implementarea necesită o sortare directă a selecției, așa cum este definit mai jos. Aici, este necesar să se identifice cel mai mic element prezent în tablă și acest element este sortat în prima poziție cu, Apoi, se identifică cel de-al doilea element cel mai mic și este sortat în a doua poziție. Sortul de selecție iese din bucla sa când subpartea nesortată devine goală. Complexitatea timpului este dată ca O (n 2 ).
Luați în considerare următorul tablou:
| 63 | 26 | 13 | 23 | 12 |
1. Găsirea celui mai mic element și așezați-l la început și este schimbat cu poziția.
| 12 | 26 | 13 | 23 | 63 |
2. Al doilea element a (1) este identificat se compară cu elementul minim și se așează în a doua poziție, în mod similar, trecerea continuă.
| 12 | 13 | 26 | 23 | 64 |
Rezultat final sortat
| 12 | 13 | 23 | 26 | 64 |
Concluzie
În concluzie, acest articol s-a concentrat pe conceptele de sortare și mecanismul lor de lucru. Toate aceste tehnici de sortare folosesc concepte paralele de procesare. Sortarea formează un bloc de bază în structurarea algoritmilor pentru a rezolva problemele datelor din lumea reală prin sortarea setului de valori în funcție de cerințe.
Articole recomandate
Acesta este un ghid pentru Sortarea în C ++. Aici discutăm Introducere și Sintaxă cu exemple împreună cu Cum funcționează. Puteți parcurge și alte articole sugerate pentru a afla mai multe -
- Sortare în Tableau
- Iterator în C ++
- Funcții Array în C
- Sortare pentru grămadă în C
- Cum se realizează sortarea în PHP?
- Sort de grămadă în Python
- Iterator în Java
- Top 11 caracteristici și avantaje ale C ++
- Iterator în Python | Beneficii și exemple de Python