MOJA PASJA - PROGRAMOWANIE
   Dzisiaj jest Sobota, 4 lutego, 2012r. Ostatnia aktualzacja miała miejsce: 10 grudnia 2006r. Homepage

Programowanie: Artykuły * FAQ * Download * Komponenty * Książki WWW: Artykuły * Narzędzia * Kursy * Darmowe * FAQ * Skrypty * Ksiązki Off-Topic: Aforyzmy * Humor Inne: Forum * Wiki * Liczniki * Linki * Chat * Grafika * Video * Inne


Sortowanie bąbelkowe




   Sortowanie bąbelkowe to jeden z najprostyszych algorytmów sortowania. Zaraz wyjaśni się skąd ta dziwna nazwa :). Nie jest to niestety algorytm zbyt szybki. Jego złożoność to O(n2) czyli jeżeli dostanie 20 liczb do posortowania, to w najgorszym przypadku będzie musiał wykonać 400 operacji.

   No a teraz najważniejsze - jak to działa. Otóż bardzo prosto:

  • Porównujemy po kolei elementy ze sobą sąsiadujące czyli 1 z 2, 2 z 3, 3 z 4, 4 z 5, 5 z 6 itd.
  • Jeżeli element po lewej jest wiekszy od elementu po prawej to zamieniamy je ze sobą (jeżeli nie, to nic nie robimy)
  • Całość powtarzamy tyle razy, ile jest elementów, lub jeżeli po porównaniu wszystkich elementów nie zamieniliśmy żadnych miejscami
   Myślę że problemów ze zrozumieniem nie miałeś, no ale prześledźmy działanie algorytmu na przykładzie. Załóżmy że mamy taką oto 7 elementową tablicę:
58233317120


   No i teraz wykonywanie kroków 1 i 2. Elementy porównywane są podkreślone:

58233317120

25833317120

23358317120

23335817120

23331758120

23331715820

23331712058

   Przypatrz się teraz liczbie 58. Widzisz jej drogę ? Wędruje po kolei na właściwe miejsce, na górę. W następnym przebiegu lecieć do góry będzie liczba 33 itd. Stąd właśnie nazwa algorymu. Tak jak bąbelki w wodzie wypływają do góry tak tutaj największe liczby "wypływają" na koniec tablicy.

   Przy okazji można zauważyć sporą wadę tego algorytmu. Tzw. puste przebiegi. Po pewnym czasie początkowe indeksy tablicy są już uporządkowane, a nasz algorytm dalej za każdym razem "jeździ" po nich i porównuje liczby. Można go poprawić, zapamiętując za każdym razem indeks tablicy od którego liczby są już uporządkowane, ale nie zmieni to klasy algorytmu, nadal będzie to algorytm klasy O(n2).

   No i to chyba tyle. Pozostaje jesze sprawa implementacji. Samam funkcja sortujaca jest banalnie prosta:

void babel(int *tab, int n)
{

   for (int i=0; i<n; i++)
   {
      for (int j=0; j<n-1; j++)
      {
         if (tab[j]>tab[j+1])
         {
            int tmp;
            tmp = tab[j];
            tab[j] = tab[j+1];
            tab[j+1] = tmp;
         }
      }
   }

}


   Przykładowy program wczytujący tablicę, i wyświetlający ją w postaci posortowanej możesz pobrać tutaj.

   Wasze opinie:
   Średnia ocena: 4.04/10 (535 głosów)
   
   Liczba komentarzy: 54104 (pokaż wszystkie)Skomentuj !   

Autor: Hoodia Data dodania: 2009-03-22
Thank You!, Buy Klonopin, tpaak, Phentermine , 6689, Order Klonopin, 605, Winston Cigarettes, devtub, Xanax , sntcx,

Autor: QdOJQtkpskPXbBAData dodania: 2009-03-22
rzvunscy, comprare viagra, tujsgmti, viagra vente, ftubmxwk, compra cialis, awtzclgt, viagra bestellen, jztdtqmj,

Autor: TramadolData dodania: 2009-03-22
I like your work!, Adipex, :OOO, Buy Viagra, %]], Buy Viagra, nlh, Phentermine, :-]], Buy Ultram, pfcrcy,

Autor: ZQAYbYzxJhqUOOReBsvData dodania: 2009-03-22
stuchujz, goedkope cialis, ywwfvssh, viagra, exnnpitf, cialis, oidvarko, cialis vente, aapcbokx,

Autor: jdShMfeNLData dodania: 2009-03-22
comment6, Cialis, 49574, Order Viagra, =-[[,

Autor: PhentermineData dodania: 2009-03-22
I like your work!, Buy Klonopin, vkipmt, Buy Ultram, jswbcy, Hoodia Weight Loss, lprn, Xanax, 8-OO, Ambien , zfaxa,

Autor: HoodiaData dodania: 2009-03-22
I like your work!, Buy Ultram, %-OOO, Buy Tramadol, 8[, Buy Ativan, :-((, Buy Diazepam, 563567, Hoodia, 402508,



Stronę przygotował: Kacper Cieśla (comboy). Wszelkie prawa zastrzeżone.
Reklama * Zgłoś błąd * Kontakt * Hosting * O stronie * Sponsoring
Czas generowania strony: 0.15s