Introducere în sortarea algoritmilor în Java
Sortarea informațiilor într-o anumită ordine, adesea într-un cadru asemănător unui tablou, înseamnă să le aranjați. Puteți utiliza diferite cerințe de secvență, cele populare sunt sortarea numerelor de la cel puțin la cel mai mare sau invers, sau sortarea lexicografică a șirurilor. Vom acoperi diferiți algoritmi, de la alternative ineficiente, dar intuitive, până la algoritmi eficienți implementați efectiv în Java și în alte limbi, dacă sunteți interesat de modul de funcționare a sortării.
Algoritmi de sortare diferiți în java
Există algoritmi de sortare diferiți și nu toți sunt la fel de eficienți. Pentru a le compara și pentru a vedea care sunt cele mai bune performanțe, vom analiza complexitatea timpului.
- Sortare inserție
- Sort de bule
- Sortare selecție
- Sortare Merge
- heapsort
1. Sortare inserție
Conceptul din spatele sortării de inserție împarte intervalul în subarbele care sunt sortate și nesortate. Porțiunea clasificată este la începutul duratei 1 și se potrivește cu prima componentă (partea stângă) din tablou. Ne deplasăm prin tablou și extindem partea clasificată a tabloului cu o componentă în timpul fiecărei iterații. Când ne extindem, poziționăm elementul proaspăt în sub-tablă sortată. Facem acest lucru mișcând toate elementele la dreapta, până când descoperim că nu trebuie să schimbăm prima componentă. Când porțiunea îngroșată este sortată în ordine crescătoare, de exemplu, în următorul tablou, apare:
- 3 5 7 8 4 2 1 9 6: Luați în considerare 4 și introducerea acestui lucru este ceea ce avem nevoie. Ne schimbăm de la 8> 4
- 2. 3 5 7 x 8 2 1 9 6
- 3 5 x 7 8 2 1 9 6
- 3 x 5 7 8 2 1 9 6
- 3 4 5 7 8 2 1 9 6
Cod:
public class InsertionSortEx (
public static void insertionSort(int() arr) (
for (int x = 1; x < arr.length; x++) (
int current = arr(x);
int y = x - 1;
while(y >= 0 && current < arr(y)) (
arr(y+1) = arr(y);
y--;
)
arr(y+1) = current;
)
)
public static void main(String a())(
int() arr1 = (3, 5, 7, 8, 4, 2, 1, 9, 6);
System.out.println("Before Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
System.out.println();
insertionSort(arr1);//sorting array using insertion sort
System.out.println("After Insertion Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
)
)
ieşire:
Urmând această metodă, o componentă a extins partea sortată, acum avem cinci în loc de patru elemente. Fiecare iterație face acest lucru și întregul tablou va fi sortat până la sfârșit.
Notă: Acest lucru se datorează faptului că trebuie să transferăm întreaga listă clasificată unul câte unul în fiecare iterație, care este O (n). Pentru fiecare componentă din fiecare tabel, trebuie să facem acest lucru, ceea ce implică faptul că este legat O (n 2 ).2.2. Sortare cu bule
Dacă bula nu este în ordinea cerută, funcționează prin înlocuirea componentelor vecine. Aceasta se repetă până când toate componentele sunt în ordine de la începutul tabloului. Știm că dacă reușim să facem întreaga iterație fără swap, toate elementele în comparație cu elementele lor adiacente erau în ordinea dorită și, prin extensie, întregul tablou. Motivul algoritmului de sortare a bulelor este că numerele „bule” în „sol”. Dacă, după o anumită sumă, treceți din nou prin instanță (4 este o bună instanță), veți observa că numărul este încet. se deplasează spre dreapta.
Pașii pentru sortarea bulelor sunt următoarele:
- 4 2 1 5 3: Aici, primele două numere nu sunt în ordinea corectă, de aceea trebuie să sortăm ambele numere.
- 2 4 1 5 3: După aceea, următoarea pereche de număr nu este, de asemenea, în ordinea corectă. Deci sortarea apare din nou.
- 2 1 4 5 3: Aceste două sunt în ordinea corectă, 4 <5, prin urmare, nu este necesar să le schimbăm.
- 2 1 4 5 3 : din nou trebuie să schimbăm pentru o ordine corectă.
- 2 1 4 3 5: Iată tabloul rezultat după o iterație.
- Trebuie să repetăm din nou acest proces până când numerele sunt în ordine corectă.
Cod:
public class BubbleSortExample (
public static void bubbleSort(int() arr) (
int n = arr.length;
int tmp = 0;
for(int x=0; x < n; x++)(
for(int y=1; y < (nx); y++)(
if(arr(y-1) > arr(y))(
//swap elements
tmp = arr(y-1);
arr(y-1) = arr(y);
arr(y) = tmp;
)
)
)
)
public static void main(String() args) (
int arr() =(4, 2, 1, 5, 3);
System.out.println("Array Before Bubble Sort");
for(int x=0; x < arr.length; x++)(
System.out.print(arr(x) + " ");
)
System.out.println();
bubbleSort(arr);
System.out.println("Array After Bubble Sort");
for(int x=0; x < arr.length; x++)(
System.out.print(arr(x) + " ");
)
)
)
ieşire:
3. Sortare selecție
Selecție Sortare împarte tabloul într-o serie de clasificări care nu sunt sortate. De data aceasta, însă, subarraya de sortare este formată prin inserarea la sfârșitul tabloului sortat a elementului minim al subariei nesortate, prin schimbarea:
- 3 5 1 2 4
- 1 5 3 2 4
- 1 2 3 5 4
- 1 2 3 5 4
- 1 2 3 4 5
- 1 2 3 4 5
Cod:
public class SelectionSortEx (
public static void selectionSort(int() arr)(
for (int x = 0; x < arr.length - 1; x++)
(
int indx = x;
for (int y = x + 1; y < arr.length; y++)(
if (arr(y) < arr(indx))(
indx = y;
)
)
int smallNumber = arr(indx);
arr(indx) = arr(x);
arr(x) = smallNumber;
)
)
public static void main(String a())(
int() arr1 = (3, 5, 1, 2, 4);
System.out.println("Before Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
System.out.println();
selectionSort(arr1);
System.out.println("After Selection Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
)
)
ieşire:
4. Sortare Merge
Merge Sort utilizează recursivitatea pentru a remedia problema divizării și metoda de cucerire mai eficient decât algoritmii descriși anterior.
Acest arbore arată modul în care funcționează apelurile recursive. Săgețile marcate cu săgeata în jos sunt tablourile pentru care apelăm funcție în timp ce topim matricele săgeată. Apoi urmați săgeata până la marginea copacului și apoi reveniți și îmbinați. Avem o gamă de 3 5 3 1, așa că o împărțim în 3 5 4 și 2 1. Le împărțim în părțile lor pentru a le sorta. Începem să fuzionăm și să le sortăm pe măsură ce mergem când ajungem în fund.
Cod:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class MergeSort (
static void merge(int() array, int lowval, int midval, int highval)(
int x, y, k;
int() c= new int(highval-lowval+1);
k = 0;
x=lowval;
y=midval+1;
while(x<=midval && y<=highval)(
if(array(x)<=array(y))(
c(k++) = array(x++);
)
else(
c(k++) = array(y++);
)
)
while(x<=midval)(
c(k++) = array(x++);
)
while(y<=highval)(
c(k++) = array(y++);
)
k=0;
for(x = lowval; x<=highval; x++)(
array(x) = c(k++);
)
)
static void mergeSort(int() array, int lowval, int highval)(
if(highval-lowval+1>1)(
int midval = (lowval+highval)/2;
mergeSort(array, lowval, midval);
mergeSort(array, midval+1, highval);
merge(array, lowval, midval, highval);
)
)
public static void main(String() args) (
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
int size;
System.out.println("Enter the array");
try (
size = Integer.parseInt(r.readLine());
) catch (Exception e) (
System.out.println("Please Enter valid Input");
return;
)
int() array = new int(size);
System.out.println("Enter array elements");
int x;
for (x = 0; x < array.length; x++) (
try (
array(x) = Integer.parseInt(r.readLine());
) catch (Exception e) (
System.out.println("An error Occurred");
)
)
System.out.println("After Sorting");
System.out.println(Arrays.toString(array));
mergeSort(array, 0, array.length-1);
System.out.println("Before Merge Sorting");
System.out.println(Arrays.toString(array));
)
)
În acest program, am solicitat utilizatorului să introducă date de intrare. Ieșirea va fi ordonată în funcție de intrarea utilizatorului.
ieşire:
5. Sortare la grămadă
Mai întâi, trebuie să cunoașteți cadrul pe care Heapsort operează - hald-ul, pentru a înțelege de ce funcționează. Vom vorbi în mod special despre un morman binar, dar puteți generaliza acest lucru și la alte construcții de grămezi. Un morman este un copac care îndeplinește proprietatea mormanului și anume că toți copiii săi au relații cu fiecare nod. De asemenea, o grămadă trebuie să fie aproape terminată. Un binar de profunzime d aproape completă are o subtree d-1, cu aceeași rădăcină și fiecare nod are o subtree completă, stângă, cu o stânga descendentă.
Cu alte cuvinte, obțineți un număr mai mic și mai mic (min-heap) sau mai mare și mai mare (max-heap) atunci când vă deplasați în jos. Iată o instanță de maximă încărcare:
- 6 1 8 3 5 2 4 : Aici, ambele copii sunt mai mici decât părintele, deci nu trebuie să schimbăm nimic.
- 6 1 8 3 5 2 4: Aici, 5> 1, trebuie să le schimbăm. Trebuie să neapărat pentru 5.
- 6 5 8 3 1 2 4: Ambele numere ale copiilor sunt mai mici, toate rămân la fel.
- 6 5 8 3 1 2 4: Aici, 8> 6, prin urmare, ar trebui să le schimbăm.
- 8 5 6 3 1 2 4: După această iterație, vom obține acest rezultat.
După repetarea acestui proces din nou, vom obține următoarele rezultate:
- 8 5 6 3 1 2 4
- 4 5 6 3 1 2 8 : Schimbarea
- 6 5 4 3 1 2 8 : Heapify
- 2 5 4 3 1 6 8 : Schimbarea
- 5 2 4 2 1 6 8 : Heapify
- 1 2 4 2 5 6 8 : Schimbarea
Cod:
public class HeapSort
(
public void sort(int arr())
(
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr(0);
arr(0) = arr(x);
arr(x) = tmp;
heapify(arr, x, 0);
)
)
void heapify(int arr(), int n, int x)
(
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L arr(largest))
largest = L;
if (r arr(largest))
largest = r;
if (largest != x)
(
int swap = arr(x);
arr(x) = arr(largest);
arr(largest) = swap;
heapify(arr, n, largest);
)
)
static void printArray(int arr())
(
int n = arr.length;
for (int x=0; x System.out.print(arr(x)+" ");
System.out.println();
)
public static void main(String args())
(
int arr() = (6, 1, 8, 3, 5, 2, 4);
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
)
)public class HeapSort
(
public void sort(int arr())
(
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr(0);
arr(0) = arr(x);
arr(x) = tmp;
heapify(arr, x, 0);
)
)
void heapify(int arr(), int n, int x)
(
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L arr(largest))
largest = L;
if (r arr(largest))
largest = r;
if (largest != x)
(
int swap = arr(x);
arr(x) = arr(largest);
arr(largest) = swap;
heapify(arr, n, largest);
)
)
static void printArray(int arr())
(
int n = arr.length;
for (int x=0; x System.out.print(arr(x)+" ");
System.out.println();
)
public static void main(String args())
(
int arr() = (6, 1, 8, 3, 5, 2, 4);
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
)
)
ieşire:
Puteți vizualiza dintr-un punct la un nivel al graficului, de la stânga la dreapta. Ceea ce am obținut aici este că atunci când avem componenta kth în tablou, poziția copiilor săi este 2 \ * k + 1 și 2 \ * k + 2 (presupunând că indexarea începe de la 0). Acest lucru poate fi monitorizat de către dvs. Poziția părintelui este întotdeauna (k-1) / 2 pentru componenta kth. Puteți „bloca maxim” orice gamă, deoarece știți asta. Verificați dacă unul dintre copiii săi este mai mic decât cel pentru fiecare componentă. Dacă da, împerecheați un părinte și repetați acest pas recursiv cu părintele.
Notă: Deoarece iterarea pentru-bucle pe întregul tablou face heapSort) (evident O (N), ar crea complexitatea generală a lui Heapsort O. (nlog n). Heapsort are un tip la fața locului, ceea ce înseamnă că necesită O ( 1) mai mult spațiu decât Merge Sort, dar are unele dezavantaje, cum ar fi paralelele care sunt dure.Concluzie - Sortarea algoritmilor în Java
Sortarea este o procedură foarte răspândită cu seturi de date, fie pentru analize suplimentare, căutarea rapidă cu algoritmi mai eficienți care se bazează pe informații sortate, filtrarea informațiilor etc. Sortarea este avizată de mai multe limbi și adesea interfețele obscurează ceea ce face programatorul.
Articole recomandate
Acesta este un ghid pentru Sortarea algoritmilor în Java. Aici discutăm diferite tipuri de sortare în Java împreună cu algoritmii lor. De asemenea, puteți parcurge și alte articole sugerate -
- Fuzionarea algoritmilor de sortare în Java
- JComboBox în Java
- StringBuffer în Java
- JTextField în Java
- Sort de grămadă în Python
- Algoritmi de sortare rapidă în Java
- Ghid complet de sortare în C # cu exemple
- Sortarea algoritmilor în JavaScript
- Ghid pentru exemple de algoritm C ++
- Ghid complet pentru sortarea algoritmilor în Python