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.
Să aruncăm o privire mai atentă asupra intrării și ieșirii sortării prin inserție:
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ă.
- 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].
- Sortare numerică (ordine crescătoare): [1, 2, 3, 4, 5]
- Sortare numerică (ordine descrescătoare): [5, 4, 3, 2, 1]
- Sortare alfabetică: [a, b, c, d]
Î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 întrearr[1]
și arr[n]
unde n
este 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 matrice1. 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-1
trebuie să fie mai mare decâtj
indicele
j
.
5. Sortarea matricei
După ce ați configurat bucla while, valorilej
și j-1
vor 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:
int key = sort_arr[j];
sort_arr[j] = sort_arr[j-1];
sort_arr[j-1] = key;
j = j-1;
Sortarea unui ArrayList
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ă
Element
clasă 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.
4, 2, 6, 7, 0, 5, 9, 1, 8, 3, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
GO TO FULL VERSION