bubble sort java java sorting algorithms code examples
Denna handledning kommer att förklara Bubblesortering i Java tillsammans med Major Java-sorteringsalgoritm, bubbelsortering och kodexempel:
En sorteringsalgoritm kan definieras som en algoritm eller ett förfarande för att placera element i en samling i en specifik ordning. Till exempel, om du har en numerisk samling som en ArrayList av heltal, kanske du vill ordna elementen i ArrayList i stigande eller fallande ordning.
På samma sätt kanske du vill ordna strängar i en strängsamling i alfabetisk eller lexikografisk ordning. Det är här sorteringsalgoritmerna i Java kommer in i bilden.
bästa ide för python på mac
Vad du kommer att lära dig:
Stora sorteringsalgoritmer i Java
Sorteringsalgoritmer utvärderas vanligtvis beroende på tid och rymdskomplexitet. Java stöder olika sorteringsalgoritmer som används för att sortera eller ordna samlingar eller datastrukturer.
Tabellen nedan visar de viktigaste sorteringsalgoritmerna som stöds i Java tillsammans med deras bästa / värsta fall-komplexitet.
| Tidskomplexitet | ||||
|---|---|---|---|---|
| Radix Sortera | Linjär sorteringsalgoritm. | O (nk) | O (nk) | O (nk) |
| Sorteringsalgoritm | Beskrivning | Bästa fall | Värsta fall | Genomsnittligt fall |
| Bubblesortering | Jämför det aktuella elementet med intilliggande element upprepade gånger. I slutet av varje iteration bubblas det tyngsta elementet upp på rätt plats. | På) | O (n ^ 2) | O (n ^ 2) |
| Insättningssortering | Infogar varje element i samlingen på rätt plats. | På) | O (n ^ 2) | O (n ^ 2) |
| Slå ihop sortering | Den följer delnings- och erövringsstrategin. Delar upp samlingen i enklare undersamlingar, sorterar dem och slår sedan samman allt | O (nlogn) | O (nlogn) | O (nlogn) |
| Snabb sortering | Mest effektiv och optimerad sorteringsteknik. Använder dela och erövra för att sortera samlingen. | O (nlogn) | O (n ^ 2) | O (nlogn) |
| Urvalssortering | Hitta det minsta elementet i samlingen och placera det på rätt plats i slutet av varje iteration | O (N ^ 2) | O (N ^ 2) | O (N ^ 2) |
| Heap Sort | Element sorteras efter att bygga min heap eller max heap. | O (nlogn) | O (nlogn) | O (nlogn) |
Förutom de sorteringstekniker som ges i tabellen ovan stöder Java också följande sorteringstekniker:
- Hink Sortera
- Räknar sortering
- Skalsortering
- Kombsortering
Men dessa tekniker används sparsamt i praktiska tillämpningar, så dessa tekniker kommer inte att ingå i denna serie.
Låt oss diskutera Bubble Sort Technique i Java.
Bubblesortering i Java
Bubblesortering är den enklaste av alla sorteringstekniker i Java. Denna teknik sorterar samlingen genom att jämföra två angränsande element upprepade gånger och byta dem om de inte är i önskad ordning. Således, i slutet av iterationen, blir det tyngsta elementet bubblat för att hävda sin rättmätiga position.
Om det finns n element i lista A som ges av A (0), A (1), A (2), A (3), ... .A (n-1), jämförs A (0) med A (1 ), A (1) jämförs med A (2) och så vidare. Efter att ha jämfört om det första elementet är större än det andra byts de två elementen om de inte är i ordning.
Bubble Sort Algorithm
Den allmänna algoritmen för Bubblesorteringsteknik ges nedan:
Steg 1: För i = 0 till N-1 upprepar du steg 2
Steg 2: För J = i + 1 till N - upprepar jag
Steg 3: om A (J)> A (i)
Byt A (J) och A (i)
(Slut på inre för slinga)
(Avsluta om yttre för slinga)
Steg 4: Utgång
Låt oss nu demonstrera Bubblesorteringstekniken med ett illustrativt exempel.
Vi tar en matris av storlek 5 och illustrerar algoritmen för bubblasortering.
Sortera en matris med hjälp av bubblasortering
Följande lista ska sorteras.
hur kör jag swf-filer
Som du kan se ovan är matrisen helt sorterad.
Ovanstående illustration kan sammanfattas i tabellform enligt nedan:
| Passera | Osorterad lista | jämförelse | Sorterad lista |
|---|---|---|---|
| {3,6,11,4,15} | {11.4} | {3,6,4,11,15} | |
| 1 | {11, 3, 6,15,4} | {11.3} | {3,11,6,15,4} |
| {3,11,6,15,4} | {11.6} | {3,6,11,15,4} | |
| {3,6,11,15,4} | {11.15} | {3,6,11,15,4} | |
| {3,6,11,15,4} | {15.4} | {3,6,11,4,15} | |
| två | {3,6,11,4,15} | {3,6} | {3,6,11,4,15} |
| {3,6,11,4,15} | {6.11} | {3,6,11,4,15} | |
| 3 | {3,6,4,11,15} | {3,6} | {3,6,4,11,15} |
| {3,6,4,11,15} | {6.4} | {3,4,6,11,15} | |
| {3,4,6,11,15} | SORTERAD |
Som visas i exemplet ovan, bubblar det största elementet upp till sin rätta position med varje iteration / pass. I allmänhet passerar när vi når N-1 (där N är ett totalt antal element i listan); vi sorterar hela listan.
Exempel på bubblasorteringskod
Nedanstående program visar Java-implementeringen av bubblasorteringsalgoritmen. Här upprätthåller vi en rad siffror och använder två för loopar för att korsa genom intilliggande element i arrayen. Om två intilliggande element inte är i ordning byts de ut.
import java.util.*; class Main{ // Driver method to test above public static void main(String args()) { //declare an array of integers int intArray() = {23,43,13,65,11,62,76,83,9,71,84,34,96,80}; //print original array System.out.println('Original array: ' + Arrays.toString(intArray)); int n = intArray.length; //iterate over the array comparing adjacent elements for (int i = 0; i intArray(j+1)) { int temp = intArray(j); intArray(j) = intArray(j+1); intArray(j+1) = temp; } //print the sorted array System.out.println('Sorted array: ' + Arrays.toString(intArray)); } } Produktion:
Originalmatris: (23, 43, 13, 65, 11, 62, 76, 83, 9, 71, 84, 34, 96, 80)
Sorterad matris: (9, 11, 13, 23, 34, 43, 62, 65, 71, 76, 80, 83, 84, 96)
Vanliga frågor
F # 1) Vilka är sorteringsalgoritmerna i Java?
Svar: Sorteringsalgoritmen kan definieras som en algoritm eller procedur med vilken elementen i en samling kan ordnas eller ordnas på önskat sätt.
Nedan följer några av de sorteringsalgoritmer som stöds i Java:
- Bubblesortering
- Insättningssortering
- Urvalssortering
- Slå ihop sortering
- Snabbsort
- Radix-sortering
- Heapsort
F # 2) Vad är den bästa sorteringsalgoritmen i Java?
Svar: Merge Sort ska vara den snabbaste sorteringsalgoritmen i Java. Faktum är att Java 7 internt har använt merge sort för att implementera Collections.sort () -metoden. Snabbsortering är också en annan bästa sorteringsalgoritm.
F # 3) Vad är Bubble sort i Java?
Svar: Bubblesortering är den enklaste algoritmen i Java. Bubblesortering jämför alltid två intilliggande element i listan och byter dem om de inte är i önskad ordning. Således, i slutet av varje iteration eller passering, bubblas det tyngsta elementet upp till sin rätta plats.
F # 4) Varför är Bubble sort Ntvå?
Svar: För att implementera bubblasortering använder vi två för öglor.
css intervju frågor och svar för erfarna
Det totala arbetet som utförs mäts av:
Mängden arbete som utförs med inre slinga * totalt antal gånger den yttre slingan körs.
För en lista över n element fungerar den inre slingan för O (n) för varje iteration. Den yttre slingan går för O (n) iteration. Följaktligen är det totala arbetet O (n) * O (n) = O (ntvå)
F # 15) Vilka är fördelarna med Bubble sort?
Svar: Fördelarna med Bubble Sort är följande:
- Lätt att koda och förstå.
- Få kodrader krävs för att implementera algoritmen.
- Sorteringen görs på plats, dvs. ytterligare minne krävs inte och därmed inget minnesomkostnad.
- De sorterade uppgifterna är omedelbart tillgängliga för bearbetning.
Slutsats
Hittills diskuterade vi sorteringsalgoritmen Bubble Sort i Java. Vi undersökte också algoritmen och detaljerad illustration av sortering av en array med Bubble Sort Technique. Sedan implementerade vi Java-programmet till Bubble Sort.
I nästa handledning fortsätter vi med andra sorteringstekniker i Java.
=> Kontrollera ALLA Java-handledning här.
Rekommenderad läsning
- Selection Sort In Java - Selection Sort Algorithm & Exempel
- Insertion Sort In Java - Insertion Sort Algorithm & Exempel
- Bubblesortering i C ++ med exempel
- Hur man sorterar en matris i Java - Handledning med exempel
- Java Array Length Tutorial With Code Exempel
- MongoDB Sort () -metod med exempel
- Unix Sorteringskommando med syntax, alternativ och exempel
- Java 'detta' Nyckelord: Handledning med kodexempel