SORTOWANIE BĄBELKOWE --BUBBLESORT--

CO trzeba umieć:

-- TABLICE 

//////////////////////////////////////////////////////////////////

SORTOWANIE

Sortowanie to jeden z największych problemów w informatyce, ponieważ posortowanymi danymi łatwiej się operuje, a przede wszystkim szybciej. Ale wszystko się sprowadza do tego by te nasze dane szybko posortować. Tylko co to znaczy szybko, czy 5 min jest szybko czy wolno? Chodzi o to, żeby nasz algorytm miał możliwie najlepszą złożoność. Bo zawsze nasze dane możemy sortować na lepszych komputerach, ale często inwestowanie w lepszy sprzęt jest bezsensowne, gdyż lepiej zainwestować w lepszy algorytm sortujący. Dla nas teraz, czy program sortuje 0,5s czy 1s to bez różnicy, ale przy danych, rzędu kilku milionów ta różnica może być naprawdę znacząca. Dobra miałem postraszyć, to postraszyłem, ale jak zwykle wszystko pomalutku i powoli, więc od początku :D.

1. SORTOWANIE BĄBELKOWE:

Sortowanie bąbelkowe (bubble sort) polega na porównywaniu dwóch kolejnych elementów i zamianie (jeśli są w złej kolejności). Następnie znowu porównanie następnych elementów. Po pierwszym przejściu tablicy jeden element (ostatni), będzie na swoim miejscu. Następnie znowu przechodzimy tablicę, ale o ten jeden element mniejszą, bo jest już częściowo uporządkowana. Czynność tą powtarzamy, aż przestaniemy robić zamiany, bo gdy program po przejściu tablicy nie zrobi żadnej zamiany to oznacza, że nasza tablica jest uporządkowana.

Przykład:

tablica: [4,2,5,1,7], chcemy by tablica była ostawiona rosnąco.

[4,2,5,1,7] porównujemy ze sobą dwa elementy (4 większe od 2) zamieniamy miejscami.

[2,4,5,1,7] porównujemy kolejne dwa elementy dobra kolejność

[2,4,5,1,7] 5 większe od 1, zamieniamy

[2,4,1,5,7] dobra kolejność, zostawiamy

[2,4,1,5,7] tablica częściowo uporządkowana, ale dokonywaliśmy zmian więc powtarzamy wszystko jeszcze raz.

[2,4,1,5,7] dobra kolejność zostawiamy

[2,4,1,5,7] zamieniamy

[2,1,4,5,7] dobra kolejność

[2,1,4,5,7] kolejny element jest na swoim miejscu i znowu powtarzamy wszystko.

[2,1,4,5,7] zamieniamy miejscami elementy

[1,2,4,5,7] dobra kolejność

[1,2,4,5,7] znowu część tablicy uporządkowana, ale powtarzamy wszystko ponownie.

[1,2,4,5,7] porównujemy elementy są w odpowiedniej kolejności, więc zostawiamy. Dalej nie porównujemy, bo dalej tablica już jest uporządkowana. Nie dokonaliśmy żadnej zmiany, więc kończymy i otrzymujemy uporządkowaną tablicę.

[1,2,4,5,7]

kod:

void bubblesort( int t[], int n ){ 
 // funkcja przyjmuje jako argument tablicę i jej rozmiar 

  int i,j; // liczniki pętli 
  int tmp; // zmienna pomocnicza
  int zmiana; // zmienna przechowująca informacje o zamianie elementów 
 
  for (i=0; i<n-1; ++i) { // pętla która dba o kolejne przechodzenia tablicy 
       
  zmiana=0; // przed każdym przejściem tablicy zerowana zmienna „zamiana” 
       
  for (j=0; j<n-1-i; j++){  // pętla która przechodzi tablicę 
          if (t[j+1] < t[j]){   //porównanie sąsiadujących elementów
              
           // zamienianie elementów 
              tmp = t[j];      
              t[j] = t[j+1];
              t[j+1] = tmp; 
    //
   
              zmiana=1; // zmienna „zmiana” na 1 czyli dokonano zamiany  
          }
       }
       if(zmiana==0) break; // jeśli nie dokonano zamiany - koniec!
  }
}

Jak widać sam kod jest w zasadzie bardzo prosty. Dwie pętle które odpowiadają za przechodzenie tablicy pierwsza wykonuje się n-razy, a druga za każdy obrotem pierwszej pętli wykonuje się o 1 raz mnie, bo jak pamiętamy nasza tablica do segregowania się zmniejsza o jeden element. W drugiej pętli dokonują się zamiany jeśli zachodzi taka potrzeba, jeśli nie dokonano żadnej zamiany funkcja wychodzi za pomocą break. Jeśli pozbędziemy się zmiennej „zamiana” funkcja też będzie działać dobrze, ale może wystąpić taka sytuacja, że będziemy przechodzić już posegregowaną tablicę, a tak unikamy takiej sytuacji. Złożoność tego sortowania jest O(n^2). Czyli raczej słabo ponieważ funkcja n^2 bardzo szybko rośnie.