Algoritam sortiranja mjehurića

U ovom vodiču naučit ćete kako sortiranje mjehurića djeluje. Također ćete pronaći radne primjere mjehurića u C, C ++, Java i Python.

Razvrstavanje mjehurića algoritam je koji uspoređuje susjedne elemente i zamjenjuje njihove položaje ako nisu u željenom redoslijedu. Poredak može biti uzlazni ili silazni.

Kako sortiranje mjehurića djeluje?

  1. Polazeći od prvog indeksa, usporedite prvi i drugi element. Ako je prvi element veći od drugog, oni se zamjenjuju.
    Sada usporedite drugi i treći element. Zamijenite ih ako nisu u redu.
    Gornji postupak traje do zadnjeg elementa. Usporedite susjedne elemente
  2. Isti se postupak odvija i za preostale ponavljanja. Nakon svake iteracije, najveći element među nerazvrstanim elementima stavlja se na kraj.
    U svakoj se iteraciji uspoređivanje odvija do zadnjeg nerazvrstanog elementa.
    Niz se sortira kada su svi nerazvrstani elementi postavljeni na ispravne položaje. Usporedite susjedne elemente Usporedite susjedne elemente Usporedite susjedne elemente

Algoritam sortiranja mjehurića

 bubbleSort (niz) za i rightElement zamijeni leftElement i rightElement kraj bubbleSort

Primjeri Pythona, Java i C / C ++

Python Java C C ++ 
 # Bubble sort in Python def bubbleSort(array): # run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Asc ending Order:') print(data)
 // Bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) for (int j = 0; j  to array(j + 1)) ( // swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) ) 
 // Bubble sort in C #include void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i " to " array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printArray(data, size); )
 // Bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i to array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )

Optimizirano sortiranje mjehurića

U gornjem kodu napravljene su sve moguće usporedbe, čak i ako je niz već sortiran. Povećava vrijeme izvršenja.

Kôd se može optimizirati uvođenjem zamijenjene dodatne varijable. Nakon svake iteracije, ako tada ne dođe do zamjene, nema potrebe za izvođenjem daljnjih petlji.

U tom se slučaju zamjena varijable postavlja na false. Dakle, možemo spriječiti daljnje ponavljanje.

Algoritam za optimiziranu vrstu mjehurića je

 bubbleSort (niz) zamijenjen <- false za i rightElement zamijenjen leftElement i rightElement zamijenjen <- true kraj bubbleSort

Primjeri optimiziranog razvrstavanja mjehurića

Python Java C C + 
 # Optimized bubble sort in python def bubbleSort(array): # Run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): # swapped keeps track of swapping swapped = True for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # Swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) swapped = False # If there is not swapping in the last swap, then the array is already sorted. if swapped: break data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Ascending Order:') print(data) 
 // Optimized bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) ( // swapped keeps track of swapping boolean swapped = true; for (int j = 0; j  to array(j + 1)) ( // Swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; swapped = false; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == true) break; ) ) // Driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) ) 
 // Optimized bubble sort in C #include void bubbleSort(int arrayay(), int size) ( for (int step = 0; step < size - 1; ++step) ( // Swapped keeps track of swapping int swapped = 0; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i to arrayay(i + 1)) ( // Swap if greater is at the rear position int temp = arrayay(i); arrayay(i) = arrayay(i + 1); arrayay(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printarrayay(int arrayay(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", arrayay(i)); ) printf(""); ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printarrayay(data, size); )
 // Optimized bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( for (int step = 0; step < size - 1; ++step) ( 
  // Run loops two times: one for walking throught the array // and the other for comparison int swapped = 0; for (int i = 0; i to array(i + 1)) ( // Swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )

Složenost

Sortiranje mjehurića jedan je od najjednostavnijih algoritama za sortiranje. U algoritam su implementirane dvije petlje.

Ciklus Broj usporedbi
1. (n-1)
2. (n-2)
3. (n-3)
… …
posljednji 1

Broj usporedbi: (n - 1) + (n - 2) + (n - 3) + … + 1 = n (n - 1) / 2 gotovo jednako n 2

Složenost: O (n 2 )

Također, složenost možemo analizirati jednostavnim promatranjem broja petlji. Postoje 2 petlje pa je složenostn*n = n2

Složenost vremena:

  • Najgori složeni slučaj: Ako želimo sortirati u rastućem redoslijedu, a niz je u silaznom redoslijedu, tada se događa najgori slučaj.O(n2)

  • Složenost najboljeg slučaja:O(n)
    Ako je niz već sortiran, nema potrebe za sortiranjem.

  • Prosječna složenost slučaja: Događa se kada su elementi niza pomiješanim redoslijedom (niti uzlazno niti silazno).O(n2)

Složenost prostora: Složenost
prostora je O(1)zato što se za zamjenu koristi dodatna promjenjiva temp.

U optimiziranom algoritmu zamijenjena varijabla dodaje složenost prostora, čineći je O(2).

Aplikacije za sortiranje mjehurića

Razvrstavanje mjehurića koristi se u sljedećim slučajevima kada

  1. složenost koda nije bitna.
  2. poželjna je kratka šifra.

Zanimljivi članci...