Zbiór uporządkowany (ang. ordered set) to taki, w którym elementy występują w określonym porządku, czyli w określonej kolejności kolejności. Jeśli elementy są liczbami, to porządek może być:

• rosnący - każdy następny element zbioru jest większy od swojego poprzednika. W zbiorze nie ma elementów równych. Taki porządek nazywamy porządkiem mocnym.
  Np. {0 2 4 7 12 13 16 74 125 200 333 ...}
• malejący - każdy następny element jest mniejszy od swojego poprzednika. W zbiorze nie ma elementów równych - porządek mocny.
  Np. (100 96 64 32 15 10 8 4 2 -4 -9 -22 ... }
• niemalejący - każdy następny element jest równy lub większy od swojego poprzednika. Elementy o tych samych wartościach mogą występować wielokrotnie obok siebie. Taki porządek nazywamy porządkiem słabym.
  Np. { 1 1 1 1 1 3 4 4 5 8 12 12 12 33 40 ... }
• nierosnący - każdy następny element jest równy lub mniejszy od swojego poprzednika. Elementy o tych samych wartościach mogą się powtarzać - porządek słaby.
  Np. {100 95 75 75 75 40 23 12 12 12 12 7 6 4 2 2 2 1 1 1 ... }

Przez sortowanie będziemy rozumieć taką zmianę kolejności elementów zbioru nieuporządkowanego (permutację), aby w wyniku spełniały one założony porządek.

Algorytm sortowania bąbelkowego jest jednym z najstarszych algorytmów sortujących. Zasada działania opiera się na cyklicznym porównywaniu par sąsiadujących elementów i zamianie ich kolejności w przypadku niespełnienia kryterium porządkowego zbioru. Operację tę wykonujemy dotąd, aż cały zbiór zostanie posortowany.

Przykład:

Jako przykład działania algorytmu sortowania bąbelkowego posortujemy przy jego pomocy 5-cio elementowy zbiór liczb {5 4 3 2 1}, który wstępnie jest posortowany w kierunku odwrotnym, co możemy uznać za przypadek najbardziej niekorzystny, ponieważ wymaga przestawienia wszystkich elementów.

 5 4 3 2 1   

 4 5 3 2 1 

 4 3 5 2 1 

 4 3 2 5 1 

 4 3 2 1 5 

 4 3 2 1 5 

 3 4 2 1 5 

 3 2 4 1 5 

 3 2 1 4 5 

 3 2 1 4 5 

 3 2 1 4 5 

 2 3 1 4 5 

 2 1 3 4 5 

 2 1 3 4 5 

 2 1 3 4 5 

 2 1 3 4 5 

 1 2 3 4 5 

 1 2 3 4 5 

 1 2 3 4 5 

 1 2 3 4 5 

Posortowanie naszego zbioru wymaga 4 obiegów. Jest to oczywiste: w przypadku najbardziej niekorzystnym najmniejszy element znajduje się na samym końcu zbioru wejściowego. Każdy obieg przesuwa go o jedną pozycję w kierunku początku zbioru. Takich przesunięć należy wykonać n - 1 (n - ilość elementów w zbiorze).

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Sortowanie wykonywane jest w dwóch zagnieżdżonych pętlach. Pętla zewnętrzna nr 1 kontrolowana jest przez zmienną j. Wykonuje się ona n - 1 razy. Wewnątrz pętli nr 1 umieszczona jest pętla nr 2 sterowana przez zmienną i. Wykonuje się również n - 1 razy. W efekcie algorytm wykonuje w sumie:

obiegów pętli wewnętrznej, po których zakończeniu zbiór zostanie posortowany. Liczba obiegów jest proporcjonalna kwadratowo do liczby elementów sortowanej tablicy. Ponieważ wykonanie obiegu zajmuje pewien czas, to całkowity czas pracy algorytmu jest proporcjonalny do kwadratu liczby sortowanych elementów. Jeśli liczbę elementów zwiększymy dwa razy, to czas ich posortowania algorytmem bąbelkowym wzrośnie średnio cztery razy. Przy dużej liczbie elementów czas ten może być bardzo długi.

Sortowanie odbywa się wewnątrz pętli nr 2. Kolejno porównywany jest i-ty element z elementem następnym. Jeśli elementy te są w złej kolejności, to zostają zamienione miejscami.

Dane dla programu:

Wszystkie liczby do posortowania są całkowite i są z zakresu od 0 do 999. Pierwsza liczba określa ilość liczb, które wystąpią za nią.

100
  41 467 334 500 169 724 478 358 962 464
 705 145 281 827 961 491 995 942 827 436
 391 604 902 153 292 382 421 716 718 895
 447 726 771 538 869 912 667 299  35 894
 703 811 322 333 673 664 141 711 253 868
 547 644 662 757  37 859 723 741 529 778
 316  35 190 842 288 106  40 942 264 648
 446 805 890 729 370 350   6 101 393 548
 629 623  84 954 756 840 966 376 931 308
 944 439 626 323 537 538 118  82 929 541

// Sortowanie bąbelkowe
//----------------------

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
  // Odczytujemy ilość liczbę danych do zmiennej n

  int n; cin >> n;

  // Tworzymy tablicę n elementową na liczby do sortowania

  int t[n], i, j, x;

  // Odczytujemy dane do tablicy

  for(i = 0; i < n; i++) cin >> t[i];

  // Wyświetlamy tablicę nieposortowaną

  cout << endl << "PRZED SORTOWANIEM:" << endl;
  for(i = 0; i < n; i++) cout << setw(4) << t[i];
  cout << endl;

  // Sortujemy bąbelkowo

  for(j = 0; j < n - 1; j++)
    for(i = 0; i < n - 1; i++)
      if(t[i] > t[i+1])
      {
        x = t[i];
        t[i] = t[i+1];
        t[i+1]= x;
      }

  // Wyświetlamy tablicę posortowaną

  cout << endl << "PO SORTOWANIU:" << endl;
  for(i = 0; i < n; i++) cout << setw(4) << t[i];
  cout << endl << endl;

  return 0;
}

Idea algorytmu sortowania przez wybór jest bardzo prosta. Załóżmy, iż chcemy posortować zbiór liczbowy rosnąco. Zatem element najmniejszy powinien znaleźć się na pierwszej pozycji. Szukamy w zbiorze elementu najmniejszego i wymieniamy go z elementem na pierwszej pozycji. W ten sposób element najmniejszy znajdzie się na swojej docelowej pozycji.

W identyczny sposób postępujemy z resztą elementów należących do zbioru. Znów wyszukujemy element najmniejszy i zamieniamy go z elementem na drugiej pozycji. Otrzymamy dwa posortowane elementy. Procedurę kontynuujemy dla pozostałych elementów dotąd, aż wszystkie będą posortowane.

Przykład:

Dla przykładu posortujmy tą metodą zbiór {4 7 2 9 3}. Kolorem zielonym oznaczyliśmy elementy zbioru, które są już posortowane.

 4 7 2 9 3   

 2 7 4 9 3 

 2 7 4 9 3 

 2 3 4 9 7 

 2 3 4 9 7 

 2 3 4 9 7 

 2 3 4 9 7 

 2 3 4 7 9 

 2 3 4 7 9 

Podana metoda sortuje zbiór rosnąco. Jeśli chcemy posortować zbiór malejąco, to zamiast elementu minimalnego poszukujemy elementu maksymalnego. Pozostała część procedury sortującej nie ulega zmianie.

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Pętla zewnętrzna sterowana zmienną j wyznacza kolejne elementy zbioru o indeksach od 0 do n - 2, w których zostaną umieszczone elementy minimalne. Na początku tej pętli zakładamy, iż elementem minimalnym jest element d[j] i zapamiętujemy jego indeks w zmiennej p_min.

W pętli numer 2 sterowanej zmienną i porównujemy pozostałe elementy zbioru z elementem d[p_min]. Jeśli element zbioru d[i] jest mniejszy od elementu d[p_min], to znaleźliśmy nowy element minimalny. W takim przypadku zapamiętujemy jego pozycję w p_min i kontynuujemy pętlę wewnętrzną.

Po zakończeniu pętli wewnętrznej p_min zawiera indeks elementu minimalnego. Zamieniamy miejscami element d[j] z elementem d[p_min]. Dzięki tej operacji element minimalny znajduje się na swojej docelowej pozycji. Zwiększamy j przechodząc do kolejnego elementu zbioru i kontynuujemy pętlę zewnętrzną.

Na lekcji napiszemy program.

Dane dla programu:

100
  41 467 334 500 169 724 478 358 962 464
 705 145 281 827 961 491 995 942 827 436
 391 604 902 153 292 382 421 716 718 895
 447 726 771 538 869 912 667 299  35 894
 703 811 322 333 673 664 141 711 253 868
 547 644 662 757  37 859 723 741 529 778
 316  35 190 842 288 106  40 942 264 648
 446 805 890 729 370 350   6 101 393 548
 629 623  84 954 756 840 966 376 931 308
 944 439 626 323 537 538 118  82 929 541