Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2022 mgr Jerzy Wałaszek
I LO w Tarnowie

obrazek

Materiały dla klasy III

Sortowanie tabel

SPIS TREŚCI

Sortowanie danych (ang. data sort) jest jednym z podstawowych problemów programowania komputerów, z którym prędzej czy później spotka się każdy programista. Poniżej przedstawiamy tylko nieliczne dziedziny, w których występuje potrzeba sortowania danych:
  • sport - wyniki uzyskane przez poszczególnych zawodników należy ułożyć w określonej kolejności, aby wyłonić zwycięzcę oraz podać lokatę każdego zawodnika.
  • bank - spłaty kredytów należy ułożyć w odpowiedniej kolejności, aby wiadomo było kto i kiedy ma płacić odsetki do banku.
  • grafika - wiele algorytmów graficznych wymaga porządkowania elementów, np. ścian obiektów ze względu na odległość od obserwatora. Uporządkowanie takie pozwala później określić, które ze ścian są zakrywane przez inne ściany dając w efekcie obraz trójwymiarowy.
  • bazy danych - informacja przechowywana w bazie danych może wymagać różnego rodzaju uporządkowania, np. lista książek może być alfabetycznie porządkowana wg autorów lub tytułów, co znacznie ułatwia znalezienie określonej pozycji.

Porządek elementów

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ć:

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.

Na początek:  podrozdziału   strony 

Sortowanie bąbelkowe (ang. Buble Sort)

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.

Obieg Zbiór Opis operacji
1
 5 4 3 2 1   
Rozpoczynamy od pierwszej pary, która wymaga wymiany elementów
 4 5 3 2 1 
Druga para też wymaga zamiany elementów
 4 3 5 2 1 
Wymagana wymiana elementów
 4 3 2 5 1 
Ostatnia para również wymaga wymiany elementów
 4 3 2 1 5 
Stan po pierwszym obiegu. Zwróć uwagę, iż najstarszy element (5) znalazł się na końcu zbioru, a najmłodszy (1) przesunął się o jedną pozycję w lewo.
2
 4 3 2 1 5 
Para wymaga wymiany
 3 4 2 1 5 
Para wymaga wymiany
 3 2 4 1 5 
Para wymaga wymiany
 3 2 1 4 5 
Elementy są w dobrej kolejności, zamiana nie jest konieczna.
 3 2 1 4 5 
Stan po drugim obiegu. Zwróć uwagę, iż najmniejszy element (1) znów przesunął się o jedną pozycję w lewo. Z obserwacji tych można wywnioskować, iż po każdym obiegu najmniejszy element wędruje o jedną pozycję ku początkowi zbioru. Najstarszy element zajmuje natomiast swe miejsce końcowe.
3
 3 2 1 4 5 
Para wymaga wymiany
 2 3 1 4 5 
Para wymaga wymiany
 2 1 3 4 5 
Dobra kolejność
 2 1 3 4 5 
Dobra kolejność
 2 1 3 4 5 
Stan po trzecim obiegu. Wnioski te same.
4
 2 1 3 4 5 
Para wymaga wymiany
 1 2 3 4 5 
Dobra kolejność
 1 2 3 4 5 
Dobra kolejność
 1 2 3 4 5 
Dobra kolejność
 1 2 3 4 5 
Zbiór jest posortowany. Koniec

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).

Uwaga:

Algorytm sortowania bąbelkowego jest uważany za bardzo zły algorytm sortujący. Można go stosować tylko dla niewielkiej liczby elementów w sortowanym zbiorze (do około 5000). Przy większych zbiorach czas sortowania może być zbyt długi. Obecnie algorytm ten ma tylko znaczenie dydaktyczne, ponieważ opracowano bardziej efektywne algorytmy sortowania.

Na początek:  podrozdziału   strony 

Algorytm sortowania bąbelkowego

 

Specyfikacja problemu

Dane wejściowe

n - liczba elementów w sortowanej tablicy, n N
t[ ] - tablica n-elementowa, która będzie sortowana. Elementy tablicy mają indeksy od 0 do n - 1.

Dane wyjściowe

t[ ] - posortowana tablica n-elementowa.  Elementy tablicy mają indeksy od 0 do n - 1.

Zmienne pomocnicze

i, j - zmienne sterujące pętli, i, j ∈ N
x - zmienna wykorzystywana do zamiany miejscami elementów tablicy

Lista kroków

K01: Dla j = 0,1,...,n - 2:
    Wykonuj krok K02
K02:     Dla i = 0,1,...,n - 2:
        Jeśli t[ i ] > t[ i + 1 ],
        to x ← t[ i ], t[ i ] ← t[ i + 1 ], t[ i + 1 ] ← x
K03: Zakończ

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.

Na początek:  podrozdziału   strony 

Program sortowania bąbelkowego

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;
}
Na początek:  podrozdziału   strony 

Sortowanie przez wybór

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.

Zbiór Opis operacji
 4 7 2 9 3   
Wyszukujemy najmniejszy element w zbiorze. Jest nim liczba 2.
 2 7 4 9 3 
Znaleziony element minimalny wymieniamy z pierwszym elementem zbioru - liczbą 4
 2 7 4 9 3 
Wśród pozostałych elementów wyszukujemy element najmniejszy. Jest nim liczba 3.
 2 3 4 9 7 
Znaleziony element minimalny wymieniamy z drugim elementem zbioru - liczbą 7.
 2 3 4 9 7 
Znajdujemy kolejny element minimalny - liczbę 4.
 2 3 4 9 7 
Wymieniamy go z samym sobą - element ten nie zmienia zatem swojej pozycji w zbiorze.
 2 3 4 9 7 
Znajdujemy kolejny element minimalny
 2 3 4 7 9 
Wymieniamy go z liczbą 9
 2 3 4 7 9 
Ostatni element jest zawsze na właściwej pozycji. Sortowanie zakończone

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

n - liczba elementów w sortowanym zbiorze, n ∈ C
t[ ] - zbiór n-elementowy, który będzie sortowany. Elementy zbioru mają indeksy od 0 do n-1.

Dane wyjściowe

t[ ] - posortowany zbiór n-elementowy. Elementy zbioru mają indeksy od 0 do n-1.

Zmienne pomocnicze

i, j - zmienne sterujące pętli, i, j ∈ C
pmin - pozycja elementu minimalnego w zbiorze d[ ],  pmin ∈ C

Lista kroków

K01: Dla j = 0, 1, ..., n - 2:
    wykonuj kroki K02...K04
K02:     pminj
K03:     Dla i = j + 1,  j + 2, ..., n - 1:
        jeśli d[i] < d[pmin],
        to pmin i
K04:     d[j] ↔ d[pmin]
K05: Zakończ

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 pmin.

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

Po zakończeniu pętli wewnętrznej pmin zawiera indeks elementu minimalnego. Zamieniamy miejscami element d[j] z elementem d[pmin]. 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:

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

 

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2022 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.