Sortowanie bąbelkowe

Lekcja 13 z 26 w kursie Tablice w C++ w Coddy.

Inny sposób sortowania tablicy to sortowanie bąbelkowe. Polega on na porównywaniu każdej sąsiadującej pary liczb i zamienianiu ich miejscami, jeśli liczba po prawej stronie jest mniejsza od liczby po lewej, aż do końca.

1. Zadeklaruj zmienną o nazwie counter i zainicjalizuj ją wartością 1. Zmienna counter zlicza elementy, które są już posortowane.

2. Utwórz pętlę while z warunkiem iteracji, który działa, dopóki counter jest mniejsze od n.

int counter=1;
while(counter<n){
     
}

3. Utwórz pętlę for wewnątrz pętli while i wykonuj iteracje od 0 do n-counter. Dzieje się tak, ponieważ counter elementów jest już posortowanych i nie musimy sprawdzać ich ponownie.

int counter=1;
while(counter<n){
     for(int i=0;i<n-counter;i++){
     
     }
}

4. Następnie porównaj i-ty element z następnym, czyli elementem (i+1), a jeśli arr[i]>arr[i+1], zamień je miejscami.

Możemy zauważyć, że w pierwszej iteracji zewnętrznej pętli while największy element zostaje przesunięty na ostatnią pozycję. Dlatego pomijamy tę część w następnej iteracji i zwiększamy counter o 1.

int counter=1;
while(counter<n){
  for(int i=0;i<n-counter;i++){
    if(arr[i]>arr[i+1]){
      int temp=arr[i];
      arr[i]=arr[i+1];
      arr[i+1]=temp;
    }
  }
  counter++;
}

Analiza złożoności czasowej

Wykonujemy pętlę while n razy, a w każdej iteracji pętli while pętla for wykonuje się prawie n razy, dlatego złożoność czasowa wynosi O(n²).

Aby zobaczyć, jak algorytm działa krok po kroku.

Wizualizacja sortowania bąbelkowego

Wyzwanie

Posortuj podaną tablicę za pomocą algorytmu sortowania bąbelkowego i wypisz każdy element, którego indeks jest nieparzysty. Oddziel elementy pojedynczą spacją.

Spróbuj swoich sił

#include<iostream>
using namespace std;


int main(){
  
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
  cin>>arr[i];
}

//Code Here




return 0;

}