Sortera algoritmer i Java - Olika typer av sorteringsalgoritmer i Java

• Introduktion till sortering av algoritmer i Java

Introduktion till sortering av algoritmer i Java

Att sortera informationen i en viss ordning, ofta inom en matrisliknande ram, är att ordna dem. Du kan använda olika sekvenskrav, populära är sortering av nummer från minst till största eller vice versa, eller leksikografiskt sortering av strängar. Vi kommer att täcka olika algoritmer, från ineffektiva men intuitiva alternativ till effektiva algoritmer effektivt implementerade i Java och på andra språk om du är intresserad av hur sortering ska fungera.

Olika sorteringsalgoritmer i java

Det finns olika sorteringsalgoritmer och inte alla är lika effektiva. För att jämföra dem och se vilka som presterar bäst kommer vi att analysera deras tidskomplexitet.

1. Insättningssortering
2. Bubble Sort
3. Urvalssortering
4. Slå samman
5. HeapSort

1. Insertion Sort

Konceptet bakom Insertion Sort delar räckvidden i delområdena som är sorterade och osorterade. Den klassificerade delen är i början av varaktighet 1 och matchar den första (vänstra sidan) komponenten i matrisen. Vi rör oss genom matrisen och utvidgar den klassificerade delen av matrisen med en komponent under varje iteration. När vi expanderar placerar vi det nya elementet i den sorterade undergruppen. Vi gör detta genom att flytta alla element till höger tills vi upptäcker att vi inte behöver ändra den första komponenten. När den djärva delen sorteras i stigande ordning, till exempel i följande array, inträffar den:

1. 3 5 7 8 4 2 1 9 6: Tänk på 4 och infoga det här är vad vi behöver. Vi har flyttat sedan 8> 4
2. 2. 3 5 7 x 8 2 1 9 6
3. 3 5 x 7 8 2 1 9 6
4. 3 x 5 7 8 2 1 9 6
5. 3 4 5 7 8 2 1 9 6

Koda:

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+" ");
)
)
)

Produktion:

Efter denna metod utvidgade en komponent den sorterade delen, vi har nu fem istället för fyra element. Varje iteration gör detta och hela matrisen kommer att sorteras i slutet.

Obs: Detta beror på att vi måste överföra hela klassificerade listan en efter en i varje iteration, vilket är O (n). För varje komponent i varje tabell måste vi göra detta, vilket innebär att det är O (n 2) avgränsat.2.

2. Bubble Sort

Om bubblan inte är i önskad ordning fungerar den genom att byta ut angränsande komponenter. Detta upprepas tills alla komponenter är i ordning från början av matrisen. Vi vet att om vi lyckas göra hela iterationen utan swappar, var alla objekt jämfört med deras angränsande element i önskvärd ordning och i förlängningen hela matrisen. Anledningen till Bubble Sort-algoritmen är att siffrorna som "bubblar upp" i "marken." Om du efter ett visst belopp går igenom instansen igen (4 är en bra instans) kommer du att märka att numret långsamt flyttar till höger.

Steg för bubblasortering är följande:

1. 4 2 1 5 3: Här är 1: ^a två siffror inte i rätt ordning, därför måste vi sortera båda siffrorna.
2. 2 4 1 5 3: Efter det är nästa parpar inte heller i rätt ordning. Så sortering sker igen.
3. 2 1 4 5 3: Dessa två är i rätt ordning, 4 <5, därför finns det inget behov av att byta dem.
4. 2 1 4 5 3 : Återigen måste vi byta för rätt ordning.
5. 2 1 4 3 5: Här är den resulterande matrisen efter en iteration.
6. Vi måste upprepa denna process igen tills siffrorna är i rätt ordning.

Koda:

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) + " ");
)
)
)

Produktion:

Obs: Det kan ha hamnat i en oändlig slinga om jag använde en (i)> = a (i + 1), eftersom den anslutningen fortfarande skulle vara giltig med motsvarande komponenter och därför alltid byta dem från ett element till ett annat.

3. Val av sortering

Val av sortering delar upp matrisen i en grupp klassificeringar som inte sorteras. Den här gången bildas emellertid sorteringsdelgruppen genom att i slutet av den sorterade matrisen infogar minimumelementet i den osorterade delgruppen genom att byta:

1. 3 5 1 2 4
2. 1 5 3 2 4
3. 1 2 3 5 4
4. 1 2 3 5 4
5. 1 2 3 4 5
6. 1 2 3 4 5

Koda:

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+" ");
)
)
)

Produktion:

Obs: Minsta är O (n) för matrisstorleken eftersom alla komponenter måste kontrolleras. För varje element i matrisen måste vi hitta det minsta och göra hela processen O (n 2) begränsad.

4. Slå samman

Merge Sort använder rekursion för att fixa frågan om splittring och erövringsmetoden mer effektivt än tidigare beskrivna algoritmer.

Detta träd visar hur rekursiva samtal fungerar. Nedåtpilar markerade matriser är de matriser som vi kallar funktion för medan vi smälter upp pilmatriser. Sedan följer du pilen till trädets kant och återgår sedan och slås samman. Vi har 3 5 3 1-intervall, så vi delade upp det i 3 5 4 och 2 1. Vi delar upp dem i deras delar för att sortera dem. Vi börjar smälta och sortera dem när vi går till botten.

Koda:

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));
)
)

I detta program har vi bett användaren att mata in input. Utgången kommer att vara i sorterad ordning baserat på användarens ingång.

Produktion:

5. Heap Sort

Du måste först känna till vilken ram Heapsort fungerar - högen för att förstå varför den fungerar. Vi talar specifikt om en binär hög, men du kan också generalisera detta till andra högkonstruktioner. En hög är ett träd som uppfyller högens egendom, nämligen att alla dess barn har förhållanden till varje nod. En hög måste också vara nästan färdig. En nästan komplett d-djup-binär har en d-1-undertråd, med samma rot, och varje nod har en full, vänster subtree, med en vänster som faller.

Med andra ord får du ett lägre och lägre antal (min-hög) eller större och större (max-hög) när du flyttar nerför trädet. Här är en max-heap-instans:

1. 6 1 8 3 5 2 4 : Här är båda barnens antal mindre än föräldern, därför behöver vi inte ändra någonting.
2. 6 1 8 3 5 2 4: Här, 5> 1, måste vi byta dem. Vi måste heapify för 5.
3. 6 5 8 3 1 2 4: Båda barnens antal är mindre, allt förblir detsamma.
4. 6 5 8 3 1 2 4: Här 8> 6, därför bör vi byta dem.
5. 8 5 6 3 1 2 4: Efter denna iteration får vi detta resultat.

Efter att ha upprepat denna process igen får vi följande resultat:

• 8 5 6 3 1 2 4

1. 4 5 6 3 1 2 8 : Byta
2. 6 5 4 3 1 2 8 : Heapify
3. 2 5 4 3 1 6 8 : Byta
4. 5 2 4 2 1 6 8 : Heapify
5. 1 2 4 2 5 6 8 : Byta

Koda:

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);
)
)

Produktion:

Du kan se det från punkt till nivå på diagrammet, från vänster till höger. Vad vi uppnådde här är att när vi har den kth-komponenten i matrisen, är dess barns position 2 \ * k + 1 och 2 \ * k + 2 (förutsatt att indexeringen börjar vid 0). Detta kan övervakas av dig. Förälderns position är alltid (k-1) / 2 för den kth-komponenten. Du kan lätt "max heap up" valfritt område, eftersom du vet det. Kontrollera om ett av dess barn är lägre än det för varje komponent. Para i så fall en förälder och upprepa detta steg rekursivt med föräldern.

Obs: Eftersom iterating for-loopar över hela matrisen gör heapSort) (uppenbarligen O (N), skulle det skapa Heapsort O: s övergripande komplexitet (nlog n). Heapsort har en typ på plats, vilket betyder att den kräver O ( 1) mer utrymme än Merge Sort, men det har vissa nackdelar, som paralleller som är svåra.

Slutsats - Sortera algoritmer i Java

Sortering är ett mycket utbrett förfarande med datasätt, vare sig det är för vidare analys, snabbare sökning med effektivare algoritmer som förlitar sig på sorterad information, filtrering av information osv. Sortering stöds av flera språk och ofta döljer gränssnitten vad programmeraren gör.

Rekommenderade artiklar

Detta är en guide till sortering av algoritmer i Java. Här diskuterar vi olika typer av sortering i Java tillsammans med deras algoritmer. Du kan också gå igenom våra andra föreslagna artiklar -

1. Slå samman sorteringsalgoritmer i Java
2. JComboBox i Java
3. StringBuffer i Java
4. JTextField i Java
5. Heap Sort i Python
6. Snabbsorteringsalgoritmer i Java
7. Komplett guide till sortering i C # med exempel
8. Sortera algoritmer i JavaScript
9. Guide till exempel på C ++ algoritm
10. Komplett guide till sortering av algoritmer i Python