Sortarea matricelor este una dintre cele mai comune operațiuni pe care un începător Java ar trebui să știe să le facă. Deși matricele nu sunt întotdeauna cel mai convenabil mod de a aranja datele și acest lucru se aplică mai ales numerelor mici, conceptul din spatele sortării matricei are o mulțime de aplicații în software-ul complex și știința datelor. În această postare, vom arunca o privire mai atentă la ce este sortarea inserției. Am inclus câteva exemple și probleme de practică pentru a vă ajuta să înțelegeți pe deplin acest concept.
Ce este sortarea prin inserție?
Practic, sortarea prin inserare este un algoritm pe care dezvoltatorii îl folosesc pentru a organiza șiruri de numere mici. Împarte toate valorile în două stive - una sortată și una nesortată. Unul câte unul, numerele din teancul „nesortat” sunt alese și puse în ordinea corectă. Să aruncăm o privire mai atentă asupra intrării și ieșirii sortării prin inserție:
Intrare: o matrice A cu elemente numerice nesortate: A[0,1, n, n-2...].
Ieșire: o matrice care conține aceleași numere, dar complet sortate. Acesta este de obicei denumit B: B[0]B[1]...B[n-1].
Există o serie de moduri de a folosi sortarea prin inserare - iată cele mai populare:
Notă: dacă aveți o matrice goală sau un singleton, acestea sunt considerate a fi sortate în mod implicit.
Înțelegerea teoriei sortării prin inserție
Înainte de a explora codul din spatele sortării prin inserare, să defalcăm algoritmul folosind un limbaj non-tehnic. Deoarece vom afișa codul pentru sortare în ordine crescătoare, este logic să explicăm algoritmul pas cu pas în această postare. Pasul 1. Iterarea între arr[1]și arr[n]unde neste o valoare numerică de obicei mai mică de 10. Pasul 2. Comparați elementul pe care l-ați ales (cunoscut sub numele de key) cu numărul anterior din secvență folosind metoda sort(). Pasul 3. Dacă toate elementele sunt mai mici decât succesorii lor, repetați comparația până când găsiți o valoare mai mare. Pasul 4. Schimbați o valoare mai mare cu o poziție dincolo de cea mai mică pentru a crea o secvență ordonată. Pasul 5. Repetați procesul până când obțineți un șir de caractere sortat
Sortarea matricelor primitive
Deoarece algoritmul este una dintre cele mai simple operațiuni Java, chiar și începătorii completi nu ar trebui să aibă probleme în implementarea acestuia. Iată un ghid pas cu pas pentru sortarea unei matrice
1. Declarați o matrice pentru sortare
Pentru început, să creăm un șir de valori pe care îl vom afișa ulterior folosind Java. Pentru a utiliza sortarea prin inserare, trebuie să creați o matrice. Pentru asta folosesteint[]
int[] arrayA = {10, 14, 20, 30};
2. Folosiți sort_arr pentru a implementa algoritmul
Metoda sort_arr este una dintre cele mai comune moduri de a implementa sortarea prin inserare. În practică, arată astfel:
for(int i=0; i< sort_arr.length; ++i){
int j = i;
3. Creați o buclă și un iterator
Folosind o buclă în algoritmul de sortare prin inserare, dezvoltatorii nu trebuie să repete logica pentru fiecare element. Deși crearea buclelor pare complexă, este destul de simplă - iată un exemplu:
for(int i=0; i< sort_arr.length; ++i){
Acum că aveți o buclă funcțională, este timpul să creați un iterator care va sorta toate elementele în ordinea dorită. De acum înainte, ne vom referi la iterator ca " j".
int j = i;
4. Crearea unei bucle „while”
Când vine vorba de sortarea prin inserție, o buclă „while” este esențială pentru o matrice nouă, sortată. Pentru a-l configura pentru o sortare de inserare în ordine crescătoare, un dezvoltator trebuie să respecte două condiții:
Valoarea atribuită lui j trebuie să fie mai mare decât 0
Valoarea atribuită j-1trebuie să fie mai mare decât jindicele
De îndată ce ambele condiții din bucla while sunt adevărate, valoarea cheii matricei va fi egală cu indexul j.
5. Sortarea matricei
După ce ați configurat bucla while, valorile jși j-1vor fi schimbate până când una sau ambele condiții din bucla while eșuează. În mod similar, sortarea va fi repetată pentru fiecare valoare din bucla for până când și condițiile buclei for eșuează. Iată cum funcționează în practică procesul de sortare prin inserare:
Deși înțelegerea matematicii din spatele sortării prin inserare este importantă, atunci când vine vorba de dezvoltarea de software în viața reală, veți sorta ArrayLists mult mai mult decât secvențe în matrice primitive. Iată un ghid pas cu pas pentru sortarea unui ArrayList:
Creați o nouă Elementclasă pentru articolele care aparțin colecției.
public class Element {
private int id;
public Element(int id) {
this.id = id;
}
În cadrul unei colecții, există o compareTo()metodă - vom folosi aceasta pentru a compara ID-urile a două elemente.
public int compareTo(Element element) {
int res = 0;
if (this.id < element.getId()) {
res = -1;
}
if (this.id > element.getId()) {
res = 1;
}
return res;
}
}
Aplicați algoritmul și creați niște bucle pentru a sorta obiectele într-un loc ArrayListîn loc să le comparați.
public static void insertionSortArrayList(List<element> list) {
for (int j = 1; j < list.size(); j++) {
Element current = list.get(j);
int i = j-1;
while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
list.set(i+1, list.get(i));
i--;
}
list.set(i+1, current);
}
}
Puteți adăuga și mai multe elemente ArrayList, așa cum se arată mai jos:
List<element> list = new ArrayList<>();
// Create elements w/ IDs 0-24
for (int i = 0; i < 25; i++) {
list.add(new Element(i));
}
// To use insertion sort, shuffle the values
Collections.shuffle(list);
Acum este timpul pentru sortare:
// This helps print values before sorting
list.forEach(e -> System.out.print(e.getId() + ", "));
// Sort the list
insertionSortArrayList(list);
System.out.println();
// Display a sorted array
list.forEach(e -> System.out.print(e.getId() + ", "));
Acum să comparăm intrarea și ieșirea pentru a ne asigura că nu am făcut greșeli. Iată comparația șirului pe care l-am folosit ca exemplu.
Acum că ați înțeles acest algoritm de sortare, este timpul să vă puneți la încercare abilitățile teoretice și practice. Test de teorie #1 Vi se oferă o matrice [1, 4, 6, 8] și îi adăugați un nou element n = 7. Care este numărul de comparații pe care trebuie să le faci pentru a obține o secvență sortată de numere? Indicați valoarea finală a indexului n în tablou. Test teorie #2 La un interviu de angajare, un lider de echipă vă cere să demonstrați că introducerea sortării este o metodă ineficientă. Având în vedere un șir numeric de [0, 3, 6, 8, 9], care ar trebui să fie ordinea secvenței de intrare pentru a maximiza timpul de rulare necesar pentru sortare? Problemă de practică Sortați matricea [0, 1, 4, 5, 2, 3, 7, 9, 8] în ordinea sa crescătoare utilizând sortarea prin inserție pentru Java.
Concluzie
Cea mai mare provocare în înțelegerea tipului de inserție este înțelegerea modului în care funcționează procesul. Odată ce ați înțeles, transformarea șablonului în cod este o simplă simplă. Atâta timp cât exersați și revedeți problemele practice relevante în timp, vă veți îmbunătăți rapid viteza de sortare a inserției.
Să aruncăm o privire mai atentă asupra intrării și ieșirii sortării prin inserție:
GO TO FULL VERSION