shell sort c with examples
Tehnica de sortare a shell-ului în C ++: o prezentare generală completă.
Sortarea Shell este adesea denumită o îmbunătățire față de sortarea prin inserție. În sortarea prin inserție, luăm creșteri cu 1 pentru a compara elementele și a le pune în poziția lor corectă.
În sortare shell, lista este sortată prin descompunerea ei într-un număr de subliste mai mici. Nu este necesar ca listele să conțină elemente contigue. În schimb, tehnica sortării shell utilizează incrementul i, care este, de asemenea, numit „gap” și îl folosește pentru a crea o listă de elemente care sunt „i” separate.
=> Consultați aici pentru a explora lista completă de tutoriale C ++.
cum se dezvoltă aplicația Java în eclipsă
Ce veți învăța:
Algoritm general
Algoritmul general pentru sortarea shell-ului este dat mai jos.
shell_sort (A, N)
unde A - lista de sortat; N - gap_size
set gap_size = N, flag = 1
în timp ce gap_size> 1 sau flag = 1, repetați
începe
set flag = 0
set gap_size = (gap_size + 1) / 2
Sfârșit
pentru i = 0 la i<(N-gap_size) repeat
începe
dacă A (i + gap_size)> A (i)
swap A (i + gap_size), A (i)
set flag = 0
Sfârșit
Sfârșit
Astfel, în algoritmul de mai sus, am setat mai întâi N care este decalajul pentru sortarea matricei A folosind sortarea shell. În pasul următor, împărțim matricea în sub-tablouri folosind golul. Apoi, în pasul următor, sortăm fiecare dintre sub-tablouri, astfel încât la sfârșitul buclei vom obține o matrice sortată.
În continuare, să luăm în considerare un exemplu detaliat pentru a înțelege mai bine sortarea cochiliei folosind o reprezentare picturală.
Ilustrare
Să ilustrăm sortarea Shell cu un exemplu.
Luați în considerare următoarea matrice de 10 elemente.
Dacă oferim un spațiu de 3, atunci vom avea următoarele sub-liste cu fiecare element aflat la 3 elemente. Apoi sortăm aceste trei subliste.
Sub-listele sortate și lista rezultată pe care le obținem după combinarea celor trei subliste sortate sunt prezentate mai jos.
Matricea de mai sus pe care am obținut-o după îmbinarea subarrayurilor sortate este aproape sortată. Acum putem efectua sortarea inserției pe această listă și sortarea întregului tablou. Acest pas final este prezentat mai jos pentru referință.
După cum s-a văzut mai sus, după efectuarea sortării shell-ului și combinarea sublistelor sortate, am solicitat doar trei mutări pentru a sorta complet lista. Astfel putem vedea că putem reduce semnificativ numărul de pași necesari pentru sortarea matricei.
Alegerea incrementului pentru a crea sub-liste este o caracteristică unică a sortării shell-urilor.
Exemplu C ++
Să vedem mai jos implementarea sortării shell în C ++.
#include using namespace std; // shellsort implementation int shellSort(int arr(), int N) { for (int gap = N/2; gap > 0; gap /= 2) { for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } int main() { int arr() = {45,23,53,43,18,24,8,95,101}, i; //Calculate size of array int N = sizeof(arr)/sizeof(arr(0)); cout << 'Array to be sorted:
'; for (int i=0; i Ieșire:
Matrice de sortat:
45 23 53 43 18 24 8 95 101
Matrice după sortare shell:
8 18 23 24 43 45 53 95 101
Am folosit aceeași listă pe care am folosit-o în ilustrație și putem vedea că începem inițial prin crearea a două sub-liste și apoi reducerea diferenței. Odată ce sub listele sunt create conform golului specificat, sortăm fiecare dintre listele secundare. După ce toate listele secundare sunt sortate, obținem lista aproape sortată. Acum, această listă poate fi sortată folosind sortarea de inserție de bază, care va face foarte puține mișcări.
Apoi, să implementăm sortarea shell folosind limbajul Java.
Exemplu Java
// Java class for ShellSort class ShellSort { //function to sort the array using shell sort int sort(int arr()) { int N = arr.length; // Start with a big gap, then narrow the gap for (int gap = N/2; gap > 0; gap /= 2) { //sort sub lists created by applying gap for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } } class Main{ public static void main(String args()) { int arr() = {45,23,53,43,18,24,8,95,101}; int N = arr.length; System.out.println('Array to be sorted: '); for (int i=0; i Ieșire:
Matrice de sortat:
45 23 53 43 18 24 8 95 101
Matrice după sortare shell:
8 18 23 24 43 45 53 95 101
Am implementat aceeași logică pentru sortarea shell în ambele programe C ++ și Java. Astfel, după cum sa explicat mai sus în programul Java, împărțim mai întâi matricea în subarraiuri și apoi le sortăm pentru a obține o matrice sortată completă.
Concluzie
Sortarea Shell este algoritmul extrem de eficient care vine la o îmbunătățire față de sortarea de inserare.
În timp ce sortarea prin inserție funcționează prin incrementarea elementelor sale cu 1, sortarea shell utilizează parametrul „gap” pentru a împărți matricea în sub-tablouri ale căror elemente sunt „gap” separate. Apoi putem sorta lista individuală utilizând sortarea prin inserție pentru a obține matricea sortată completă.
Sortarea Shell se execută mai rapid decât sortarea prin inserție și face mai puține mișcări pentru a sorta matricea în comparație cu sortarea prin inserare. Următorul nostru tutorial va explora totul despre tehnica sortării heap pentru sortarea structurilor de date.
=> Vizitați aici pentru a afla C ++ de la zero.
Lectură recomandată
- Selecție Sortare în C ++ cu exemple
- Metoda MongoDB Sort () cu exemple
- Comanda de sortare Unix cu sintaxă, opțiuni și exemple
- Sortare cu bule în C ++ cu exemple
- Inserare Sortare în C ++ cu exemple
- Merge Sortează în C ++ cu exemple
- Sortare în grămadă în C ++ cu exemple
- Sortare rapidă în C ++ cu exemple