SORTOWANIE BĄBELKOWE

W tym artykule omówimy algorytm sortowania bąbelkowego. Procedura działania sortowania bąbelkowego jest najprostsza. Ten artykuł będzie bardzo pomocny i interesujący dla uczniów, ponieważ na egzaminach mogą spotkać się z pytaniem dotyczącym sortowania bąbelkowego. Dlatego ważne jest, aby omówić ten temat.

Python generuje uuid

Sortowanie bąbelkowe polega na wielokrotnym zamienianiu sąsiednich elementów, dopóki nie znajdą się one w zamierzonej kolejności. Nazywa się to sortowaniem bąbelkowym, ponieważ ruch elementów układu przypomina ruch pęcherzyków powietrza w wodzie. Bąbelki wody unoszą się na powierzchnię; podobnie elementy tablicy w sortowaniu bąbelkowym przesuwają się do końca w każdej iteracji.

Chociaż jest prosty w użyciu, jest używany przede wszystkim jako narzędzie edukacyjne, ponieważ wydajność sortowania bąbelkowego jest słaba w świecie rzeczywistym. Nie nadaje się do dużych zbiorów danych. Średnia i najgorsza złożoność sortowania bąbelkowego wynosi NA²), Gdzie N to liczba elementów.

Krótkie spodenki bąbelkowe są głównie używane tam, gdzie -

złożoność nie ma znaczenia
preferowany jest prosty i krótki kod

Algorytm

Załóżmy, że w algorytmie podanym poniżej przyr jest tablicą N elementy. Zakładane zamieniać funkcja w algorytmie zamieni wartości podanych elementów tablicy.

 begin BubbleSort(arr) for all array elements if arr[i] &gt; arr[i+1] swap(arr[i], arr[i+1]) end if end for return arr end BubbleSort

Działanie algorytmu sortowania bąbelkowego

Przyjrzyjmy się teraz działaniu algorytmu sortowania bąbelkowego.

Aby zrozumieć działanie algorytmu sortowania bąbelkowego, weźmy nieposortowaną tablicę. Bierzemy krótką i dokładną tablicę, ponieważ wiemy, jak złożona jest sortowanie bąbelkowe NA²).

Niech elementami tablicy są -

Pierwsze przejście

Sortowanie rozpocznie się od dwóch pierwszych elementów. Porównajmy je i sprawdźmy, która jest większa.

Tutaj 32 jest większe niż 13 (32 > 13), więc jest już posortowane. Teraz porównaj 32 z 26.

Tutaj 26 jest mniejsze niż 36. Dlatego wymagana jest zamiana. Po zamianie nowa tablica będzie wyglądać -

Teraz porównaj 32 i 35.

Tutaj 35 jest większe niż 32. Zatem nie ma potrzeby zamieniania, ponieważ są już posortowane.

Teraz porównanie będzie wynosić od 35 do 10.

Tutaj 10 jest mniejsze niż 35, które nie są posortowane. Zatem wymiana jest konieczna. Teraz dochodzimy do końca tablicy. Po pierwszym przejściu tablica będzie -

Teraz przejdź do drugiej iteracji.

Drugie przejście

Ten sam proces zostanie zastosowany w drugiej iteracji.

przykład danych json

Tutaj 10 jest mniejsze niż 32. Zatem wymagana jest zamiana. Po zamianie tablica będzie -

Teraz przejdź do trzeciej iteracji.

Trzecie przejście

Ten sam proces zostanie zastosowany w trzeciej iteracji.

Tutaj 10 jest mniejsze niż 26. Dlatego wymagana jest zamiana. Po zamianie tablica będzie -

Teraz przejdź do czwartej iteracji.

Czwarte przejście

Podobnie po czwartej iteracji tablica będzie -

Dlatego nie ma potrzeby zamieniania, więc tablica jest całkowicie posortowana.

Złożoność sortowania bąbelkowego

Przyjrzyjmy się teraz złożoności czasowej sortowania bąbelkowego w najlepszym, średnim i najgorszym przypadku. Zobaczymy także złożoność przestrzenną sortowania bąbelkowego.

1. Złożoność czasowa

Sprawa	Złożoność czasu
Najlepszy przypadek	NA)
Przeciętny przypadek	NA²)
Najgorszy przypadek	NA²)

NA).

NA²).

2. Złożoność przestrzeni

Złożoność przestrzeni	O(1)
Stabilny	TAK

Złożoność przestrzenna sortowania bąbelkowego wynosi O(1). Dzieje się tak dlatego, że w przypadku sortowania bąbelkowego do zamiany wymagana jest dodatkowa zmienna.
Złożoność przestrzenna zoptymalizowanego sortowania bąbelkowego wynosi O(2). Dzieje się tak dlatego, że w zoptymalizowanym sortowaniu bąbelkowym wymagane są dwie dodatkowe zmienne.

Omówmy teraz zoptymalizowany algorytm sortowania bąbelkowego.

Zoptymalizowany algorytm sortowania bąbelkowego

W algorytmie sortowania bąbelkowego porównania dokonywane są nawet wtedy, gdy tablica jest już posortowana. Z tego powodu wydłuża się czas realizacji.

Aby rozwiązać ten problem, możemy użyć dodatkowej zmiennej zamieniony. Jest ustawione PRAWDA jeśli wymagana jest zamiana; w przeciwnym razie jest ustawione na FAŁSZ.

Będzie to pomocne, jak załóżmy po iteracji, jeśli nie jest wymagana zamiana wartości zmiennej zamieniony będzie FAŁSZ. Oznacza to, że elementy są już posortowane i nie są wymagane żadne dalsze iteracje.

Ta metoda skróci czas wykonania, a także zoptymalizuje sortowanie bąbelkowe.

Algorytm zoptymalizowanego sortowania bąbelkowego

 bubbleSort(array) n = length(array) repeat swapped = false for i = 1 to n - 1 if array[i - 1] &gt; array[i], then swap(array[i - 1], array[i]) swapped = true end if end for n = n - 1 until not swapped end bubbleSort

Implementacja sortowania bąbelkowego

Przyjrzyjmy się teraz programom sortowania bąbelkowego w różnych językach programowania.

wykonaj pętlę while w Javie

Program: Napisz program realizujący sortowanie bąbelkowe w języku C.

 #include void print(int a[], int n) //function to print array elements { int i; for(i = 0; i <n; i++) { printf('%d ',a[i]); } void bubble(int a[], int n) function to implement bubble sort i, j, temp; for(i="0;" i < n; for(j="i+1;" j j++) if(a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" main () j,temp; a[5]="{" 10, 35, 32, 13, 26}; n="sizeof(a)/sizeof(a[0]);" printf('before sorting array elements are - 
'); print(a, n); bubble(a, printf('
after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-13.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in C++ language.</p> <pre> #include using namespace std; void print(int a[], int n) //function to print array elements { int i; for(i = 0; i <n; i++) { cout< <a[i]<<' '; } void bubble(int a[], int n) function to implement bubble sort i, j, temp; for(i="0;" i < n; for(j="i+1;" j j++) if(a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" main() j,temp; a[5]="{45," 1, 32, 13, 26}; n="sizeof(a)/sizeof(a[0]);" cout<<'before sorting array elements are - 
'; print(a, n); bubble(a, cout<<'
after return 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-14.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in C# language.</p> <pre> using System; public class Bubble { static void print (int[]a) //function to print array elements { int n = a.Length; int i; for (i = 0; i <n; 26 i++) { console.write (' ' + a[i]); } static void bubble (int[]a) function to implement sort int n="a.Length;" i, j, temp; for (i="0;" i < n; (j="i" 1; j j++) if (a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" public main () int[] a="{" 45, 1, 32, 13, }; ('
 before sorting array elements are - 
'); print (a); console.writeline (); after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-15.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in Java.</p> <pre> public class Bubble { static void print (int a[]) //function to print array elements { int n = a.length; int i; for (i = 0; i <n; i++) { system.out.print(a[i] + ' '); } static void bubblesort (int a[]) function to implement bubble sort int n="a.length;" i, j, temp; for (i="0;" i < n; (j="i" 1; j j++) if (a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" public main(string[] args) a[]="{35," 10, 31, 11, 26}; b1="new" bubble(); system.out.println('before sorting array elements are - b1.print(a); b1.bubblesort(a); system.out.println(); system.out.println('after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-16.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in JavaScript.</p> <pre> var a = [35, 10, 31, 11, 26]; function print() //function to print array elements { for(i = 0; i <5; i++) { document.writeln(a[i]); } document.write('before sorting array elements are - ' + <br>&apos;); print(); for(i = 0; i <5; i++) { for (j="0;" j < 5; j++) if(a[i] a[j]) temp="a[i];" a[i]="a[j];" a[j]="temp;" } document.write(' <br> After sorting array elements are - &apos; + &apos; <br>&apos;); print(); </5;></5;></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-17.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in PHP.</p> <pre> <?php $a = array(2, 45, 88, 11, 5); function printArray($a) { for($i = 0; $i < 5; $i++) { print_r($a[$i]); echo ' '; } } echo 'Before sorting array elements are - <br>&apos;; printArray($a); for($i = 0; $i <5; $i++) { for ($j="0;" $j < 5; $j++) if($a[$i] $a[$j]) $temp="$a[$i];" $a[$i]="$a[$j];" $a[$j]="$temp;" } echo ' <br> After sorting array elements are - <br>&apos;; printArray($a); ?&gt; </5;></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-18.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in python.</p> <pre> a = [35, 10, 31, 11, 26] print(&apos;Before sorting array elements are - &apos;) for i in a: print(i, end = &apos; &apos;) for i in range(0,len(a)): for j in range(i+1,len(a)): if a[j] <a[i]: temp="a[j]" a[j]="a[i]" a[i]="temp" print('
after sorting array elements are - ') for i in a: print(i, end=" " ) < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-19.webp" alt="Bubble sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the algorithm&apos;s complexity, working, optimized form, and implementation in different programming languages.</p> <hr></a[i]:></pre></n;></pre></n;></pre></n;></pre></n;>

Wyjście

Program: Napisz program realizujący sortowanie bąbelkowe w języku PHP.

 <?php $a = array(2, 45, 88, 11, 5); function printArray($a) { for($i = 0; $i < 5; $i++) { print_r($a[$i]); echo \' \'; } } echo \'Before sorting array elements are - <br>&apos;; printArray($a); for($i = 0; $i <5; $i++) { for ($j="0;" $j < 5; $j++) if($a[$i] $a[$j]) $temp="$a[$i];" $a[$i]="$a[$j];" $a[$j]="$temp;" } echo \' <br> After sorting array elements are - <br>&apos;; printArray($a); ?&gt; </5;>