Introducere privind sortarea inserției în Java
Dacă ești programator, trebuie să fi auzit deja despre sortarea multă. Sortarea înseamnă aranjarea elementelor fie în ordine crescătoare, fie în ordine descrescătoare. Există atât de mulți algoritmi de sortare disponibili pentru sortarea elementelor și fiecare algoritm are diferite modalități de sortare, complexitate diferită. Deci depinde de scenariul specific și de numărul de elemente cu privire la algoritmul care trebuie utilizat. Inserarea este, de asemenea, unul dintre algoritmii de sortare utilizați frecvent, având complexitatea O (n 2) în general și se realizează ca și cum am sorta cărțile de joc în mâinile noastre. În acest subiect, vom afla despre Sortarea inserției în Java.
Cum funcționează sortarea inserției în Java?
Să înțelegem funcționarea sortării Insertion folosind un exemplu. Să presupunem că există un tablou cu numele arr având elementele menționate mai jos:
10 5 8 20 30 2 9 7
Pasul 1 - Sortarea inserției începe cu cel de-al doilea element al tabloului, adică 5, având în vedere primul element al tabloului asortat în sine. Acum, elementul 5 este comparat cu 10, deoarece 5 este mai mic decât 10, deci 10 este deplasat cu 1 poziție înainte și 5 este introdus înainte.
Acum, tabloul rezultat este:
5 10 8 20 30 2 9 7
Pasul 2 - Acum elementul arr (2), adică 8 este comparat cu elementul arr (1), adică 10. Deoarece 8 este mai mic decât elementul său precedent 10, este deplasat cu un pas înainte de poziția sa și apoi este comparativ cu 5. Deoarece 8 este mai mare de 5, deci este introdus după el.
Atunci tabloul rezultat este:
5 8 10 20 30 2 9 7
Pasul 3 - Acum, elementul 20 este comparat cu 10, deoarece este mai mare de 10, rămâne în poziția sa.
5 8 10 20 30 2 9 7
Pasul 4 - Elementul 30 este comparat cu 20 și, din moment ce este mai mare de 20, nu s-ar face modificări și matricea rămâne așa cum este. Acum, matricea ar fi
5 8 10 20 30 2 9 7
Pasul 5 - Elementul 2 este comparat cu 30, deoarece este mai mic decât 30, este deplasat cu o poziție înainte, apoi este comparat cu 20, 10, 8, 5, unul câte unul și toate elementele sunt mutate la 1 poziție înainte. iar 2 se introduce înainte de 5.
Matricea rezultată este:
2 5 8 10 20 30 9 7
Pasul 6 - Elementul 9 este comparat cu 30, deoarece este mai mic decât 30, este comparat cu 20, 10 unul câte unul, iar elementul este deplasat 1 poziție înainte și 9 este introdus înainte de 10 și după 8. Matricea rezultată este:
2 5 8 9 10 20 30 7
Pasul 7 - Elementul 7 este comparat cu 30 și, din moment ce este mai mic decât 30, este comparat cu 30, 20, 10, 9, 8 și toate elementele sunt deplasate 1 poziție înainte una cu una și 7 se introduce înainte de 8 .Marchetul rezultat ar deveni:
2 5 7 8 9 10 20 30
În acest fel, toate elementele tabloului sunt sortate folosind sortarea de inserție începând comparația cu elementul precedent.
Exemple pentru implementarea sortării inserției în Java
Sortarea inserției în Java este un algoritm de sortare simplu potrivit pentru toate seturile de date mici.
public class InsertionSort (
public static void insertionSort(int arr()) ( for (int j = 1; j < arr.length; j++) ( int key = arr(j); int i = j-1;
while ( (i > -1) && ( arr(i) > key ) ) ( arr(i+1) = arr(i); i--; )
arr(i+1) = key;
)
)
static void printArray(int arr()) ( int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i System.out.print(arr(i) + " " );
System.out.println();
)
public static void main(String args())( int() arr1 = (21, 18, 15, 23, 52, 12, 61);
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
)
)public class InsertionSort (
public static void insertionSort(int arr()) ( for (int j = 1; j < arr.length; j++) ( int key = arr(j); int i = j-1;
while ( (i > -1) && ( arr(i) > key ) ) ( arr(i+1) = arr(i); i--; )
arr(i+1) = key;
)
)
static void printArray(int arr()) ( int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i System.out.print(arr(i) + " " );
System.out.println();
)
public static void main(String args())( int() arr1 = (21, 18, 15, 23, 52, 12, 61);
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
)
)
ieşire:
12 15 18 21 23 52 61
Explicaţie:
În programul de mai sus al Sortării inserarii, funcția insertionSort () este utilizată pentru a sorta elementele tabloului original. Sortarea începe de la al doilea element, deoarece primul element consideră că este sortat în sine. Deci bucla de „j” pornește de la indexul 1 al tabloului. „i” este variabila care ține evidența indexului chiar înainte de „j” pentru a compara valoarea. ” cheie 'este variabila care deține valoarea elementului curent care urmează să fie aranjat în poziție sortată. while () bucla este executată dacă valoarea curentă este mai mică decât valoarea din stânga, astfel încât schimbarea elementelor poate fi procesată și la finalul inserției elementului curent în poziția corectă. Funcția printArray () este utilizată pentru a imprima în cele din urmă tablele sortate.
1. Cel mai bun caz
În sortarea de inserție, cel mai bun caz ar fi atunci când toate elementele tabloului sunt deja sortate. Deci, atunci când orice element este comparat cu cel mai stânga element, acesta este întotdeauna mai mare și, prin urmare, nu se va prelucra schimbarea și inserarea elementelor. În acest caz, cea mai bună complexitate a cazului ar fi liniară, adică O (n).
2. Cazul cel mai rău
În codul de introducere de mai sus, cel mai rău caz ar fi atunci când tabloul este în ordine inversă, astfel încât de fiecare dată când elementul este comparat cu elementul său din stânga, acesta este întotdeauna mai mic și apoi comparat cu toate elementele care au loc și se schimbă. iar inserția se face. În acest caz, complexitatea sortării de inserție este O (n 2).
3. Caz mediu
Chiar și într-un caz mediu, sortarea de inserție are O (n 2) complexitate în care unele elemente nu necesită deplasare, în timp ce unele elemente sunt mutate din pozițiile lor și se face inserția în poziția corectă.
4. Cea mai bună utilizare
Sortarea de inserție este cel mai bine de utilizat atunci când dimensiunea unui tablou nu este foarte mare sau trebuie să fie sortate doar un număr mic de elemente în care sunt sortate aproape toate elementele și trebuie făcute doar unele modificări. Sortarea de inserție este unul dintre algoritmii cei mai rapizi pentru tabloul de dimensiuni mici, chiar mai rapid decât Sortarea rapidă. De fapt, quicksort folosește sortarea Insertion atunci când sortează părțile sale mici din tablou.
Concluzie
Explicația de mai sus arată în mod clar funcționarea și implementarea Sortării inserției în Java. În alte limbaje de programare, logica pentru a efectua sortarea Insertion rămâne aceeași, doar modificările de sintaxă. Înainte de a implementa orice algoritm de sortare, este foarte important să facem o anumită analiză a scenariului în care sortarea trebuie făcută, întrucât nu orice algoritm de sortare se încadrează în toate scenariile.
Articole recomandate
Acesta este un ghid pentru sortarea inserțiilor în Java. Aici vom discuta despre cum funcționează sortarea inserției în Java cu exemple pentru implementarea sortării inserției în Java. De asemenea, puteți arunca o privire la următoarele articole pentru a afla mai multe -
- Rădăcina pătrată în Java
- BorderLayout în Java
- Numărul invers în Java
- StringBuffer în Java
- Rădăcina pătrată în PHP
- Rădăcina pătrată în JavaScript
- Ghid pentru Top 6 Sortarea algoritmilor din Python