bubble sort c with examples
Bubblesorteringsteknik i C ++.
Bubble Sort är den enklaste sorteringstekniken.
I bubblasorteringstekniken jämförs vart och ett av elementen i listan med dess intilliggande element. Således om det finns n element i lista A, 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 sedan.
=> Besök här för en komplett C ++ - kurs från experter.
Vad du kommer att lära dig:
funktionell testning och icke funktionell testning
- Bubblesorteringsteknik
- Illustration
- C ++ Exempel
- Java-exempel
- Komplexitetsanalys av bubblasorteringsalgoritmen
- Slutsats
- Rekommenderad läsning
Bubblesorteringsteknik
Med hjälp av bubblasorteringstekniken görs sortering i pass eller iteration. Således i slutet av varje iteration placeras det tyngsta elementet på rätt plats i listan. Med andra ord, det största elementet i listan bubblar upp.
Vi har gett en allmän algoritm för bubblasorteringsteknik nedan.
Allmän algoritm
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
Här är en pseudokod för bubblasorteringsalgoritm, där vi korsar listan med två iterativa slingor.
I den första slingan börjar vi från 0thelement och i nästa slinga börjar vi från ett intilliggande element. I den inre loopkroppen jämför vi var och en av de intilliggande elementen och byter dem om de inte är i ordning. I slutet av varje iteration av den yttre slingan bubblar det tyngsta elementet upp i slutet.
Pseudokod
Procedure bubble_sort (array , N) array – list of items to be sorted N – size of array begin swapped = false repeat for I = 1 to N-1 if array[i-1] > array[i] then swap array[i-1] and array[i] swapped = true end if end for until not swapped end procedure
Ovanstående är pseudokoden för bubblasorteringsteknik. Låt oss nu illustrera denna teknik med hjälp av en detaljerad illustration.
Illustration
Vi tar en matris av storlek 5 och illustrerar algoritmen för bubblasortering.
Array helt sorterad.
Ovanstående illustration kan sammanfattas i tabellform enligt nedan:
Passera | Osorterad lista | jämförelse | Sorterad lista |
---|---|---|---|
{5,0,10,12,15} | {10.12} | {5,0,10,12,15} | |
1 | {10,5,15,0,12} | {10.5} | {5,10,15,0,12} |
{5,10,15,0,12} | {10.15} | {5,10,15,0,12} | |
{5,10,15,0,12} | {15.0} | {5,10,0,15,12} | |
{5,10,0,15,12} | {15.12} | {5,10,0,12,15} | |
två | {5,10,0,12,15} | {5,10} | {5,10,0,12,15} |
{5,10,0,12,15} | {10.0} | {5,0,10,12,15} | |
3 | {5,0,10,12,15} | {5,0} | {0,5,10,12,15} |
{5,0,10,12,15} | {5,10} | {5,0,10,12,15} | |
{5,0,10,12,15} | SORTERAD |
Som visas i illustrationen, med varje pass, bubblar det största elementet upp till det sista och därmed sorterar listan med varje pass. Som nämnts i inledningen jämförs varje element med sitt intilliggande element och byts ut med varandra om de inte är i ordning.
Såsom visas i illustrationen ovan placeras det största elementet i slutet av listan i slutet av det första passet, om matrisen ska sorteras i stigande ordning. För det andra passet placeras det näst största elementet på den näst sista positionen i listan och så vidare.
När vi når N-1 (där N är ett totalt antal element i listan) passerar kommer vi att sortera hela listan.
gratis databasprogramvara för Windows 10
Bubblesorteringsteknik kan implementeras på vilket programmeringsspråk som helst. Vi har implementerat bubblasorteringsalgoritmen med C ++ och Java-språk nedan.
C ++ Exempel
Låt oss se ett programmeringsexempel för att demonstrera bubblasorteringen.
#include using namespace std; int main () { int i, j,temp,pass=0; int a[10] = {10,2,0,14,43,25,18,1,5,45}; cout <<'Input list ...
'; for(i = 0; i<10; i++) { cout < Produktion:
Inmatningslista ...
10 2 0 14 43 25 18 1 5 45
Sorterad elementlista ...
0 1 2 5 10 14 18 25 43 45
Antal pass som tagits för att sortera listan: 10
Java-exempel
class Main { public static void main(String[] args) { int pass = 0; int[] a = {10,-2,0,14,43,25,18,1,5,45}; System.out.println('Input List...'); for(int i=0;i<10;i++) { System.out.print(a[i] + ' '); } for(int i=0;i<10;i++) { for (int j=0;j<10;j++) { if(a[i] Produktion:
I båda programmen har vi använt en rad med 10 element och vi sorterar den med bubblasorteringstekniken. I båda programmen har vi använt två för slingor för att itera igenom de intilliggande elementen i matrisen.
I slutet av varje pass (yttre slinga) bubblas det största elementet i arrayen upp till slutet av arrayen. Vi räknar också antalet pass som krävs för att sortera hela matrisen.
Komplexitetsanalys av bubblasorteringsalgoritmen
Från pseudokoden och illustrationen som vi har sett ovan, i bubblasorter, gör vi N-1-jämförelser i det första passet, N-2-jämförelser i det andra passet och så vidare.
Därför är det totala antalet jämförelser i bubblasortering:
I = (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1
= N (N-1) / 2
= O (ntvå) => Tidskomplexitet för bubblasorteringsteknik
Således ges de olika komplexiteterna för bubblasorteringsteknik nedan:
shell scripting intervju frågor och svar
Värsta fallets tidskomplexitet O (n 2) Komplexitet i bästa fall På) Genomsnittlig tidskomplexitet O (n 2) Rymdkomplexitet O (1)
Bubblesorteringstekniken kräver endast ett enda minnesutrymme för tempvariabeln för att underlätta byte. Därför är rymdkomplexiteten för bubblasorteringsalgoritmen O (1).
Observera att tidskomplexiteten i bästa fall för bubblasorteringsteknik är när listan redan är sorterad och det blir O (n).
Slutsats
Den största fördelen med Bubble Sort är algoritmens enkelhet. I bubblasortering, med varje passering, bubblar det största elementet upp till slutet av listan om matrisen sorteras i stigande ordning.
På samma sätt för att listan ska sorteras i fallande ordning kommer det minsta elementet att vara på sin rätta plats i slutet av varje pass.
Eftersom det är den enklaste och lättaste att implementera sorteringsteknik, används vanligtvis bubblasorter för att introducera sortering för publiken. För det andra används bubblasortering också i applikationer som datorgrafik där fyllning av polygonkanter, etc. kräver bubblasortering för att sortera hörn som kantar polygonen.
I vår kommande handledning lär vi oss mer om Selection Sort.
=> Besök här för att lära dig C ++ från Scratch.
Rekommenderad läsning
- Skalsortering i C ++ med exempel
- Urvalssortering i C ++ med exempel
- MongoDB Sort () -metod med exempel
- Unix Sorteringskommando med syntax, alternativ och exempel
- Insättningssortering i C ++ med exempel
- Slå ihop sortering i C ++ med exempel
- Heapsortering i C ++ med exempel
- Snabbsortering i C ++ med exempel