Programowanie C++

  • Strona główna
  • Programowanie C++
    • Programowanie strukturalne i obiektowe w języku C++
    • O programowaniu w życiu codziennym oraz trochę historii
  • Sortowanie
    • Sortowanie bąbelkowe
    • Sortowanie szybkie
    • Sortowanie przez wybór
    • Sortowanie przez wstawianie
    • Złożoność algorytmów sortujących
  • Instrukcje laboratoryjne
    • Instrukcje do sortowania
     W programowaniu istnieje naprawdę bardzo dużo metod sortowania. Zaczynając od najprostszych, kończąc na trudnych i skomplikowanych implementacjach algorytmów. Najważniejszym problemem przy sortowaniu jest to, że każdy algorytm sortujący zajmuje konkretną ilość pamięci obliczeniowej. Tak samo jak każdy program komputerowy, który rozwiązuje problem, posiada zasoby takie jak czas i pamięć i są one wyrażane w czasowej złożoności obliczeniowej.  Algorytmy sortujące mają różną czasową złożoność obliczeniową, a przy tym każdy z nich ma różną wydajność. Jeżeli dochodzi do analizy takiego algorytmu przypisywana jest mu klasa złożoności obliczeniowej. Istnieją trzy podstawowe klasy: 

  •  O(1) – klasa, w której algorytm bez względu na to ile danych posiada, wykonuje operacje stale, bez zmian;
  •  O(n) – klasa, w której algorytm dla każdej danej (n) wykona określoną i stałą liczbę operacji;
  •  O(n2) – klasa, w której algorytm dla każdej danej (n) wykona operacje proporcjonalnie.

        Podstawowe algorytmy sortowania posiadają złożoności czasowe typu O(n2), a dla małych wskaźników n, te czasy sortowania są do przyjęcia. Metody sortowania o takich samych elementach wartości klucza, które mogą zachować początkowy porządek nazywane są algorytmami stabilnymi.
          Aby oceniać czasową złożoność obliczeniową należy wziąć pod uwagę porównywanie dwóch danych oraz przestawianie (zamienianie) elementów. Złożoność pamięciowa to będzie ilość potrzebnej pamięci, jaką wykorzysta algorytm sortujący w celu uporządkowania danych, bez pamięci na przechowanie zawartych danych. Algorytmy, które posiadają klasę O(1) stałą są zaliczane do algorytmów sortujących w miejscu.  Są to takie implementacje, które oprócz pamięci na informacje potrzebuje stałą ilość pamięci na uporządkowanie ich.
          W celu wykonania eksperymentu, w jakim czasie sortują podane wyżej algorytmy sortowania, stworzymy program.  Aplikacja będzie wypełniać tablicę losowymi liczbami, ilość liczb podawana będzie przez użytkownika, następnie algorytmy sortujące uporządkują dane od najmniejszego do największego. Nasza aplikacja zmierzy czasy sortowań i wypisze je na ekran.

        Standardowo zaczynamy od dodania bibliotek do naszego programu, a będzie to „iostream”, „time.h”, oraz „windows.h”. Dodatkowo umieszczamy linijkę z „using namespace std”, która poinformuje kompilator o tym by wszystkie funkcje, nie wymagały użycia przedrostka „std”. 

Dodawanie bibliotek.

          Następnie definiujemy zmienne ile, zegar oraz czas. Należy to zrobić by kompilator wiedział, jakiego typu są to dane. Dalej dodajemy do programu nasze funkcje z algorytmami sortowania.

Kod przedstawiający implementację zegara oraz funkcji z algorytmami sortującymi.



        Kolejnym krokiem jest umieszczenie głównej funkcji „main”, dodanie napisów na ekran, oraz wczytanie do programu ile losowych liczb ma zawierać dynamiczna tablica.

Wypisanie tekstów na ekran.

        Następnie przypisujemy dynamiczną alokację tablicy. Robimy to po to, ponieważ z założenia nie wiemy ile wartości znajdzie się w tablicy. Nie musimy określać górnej granicy gdyż tablica będzie rozszerzać się o pola dynamicznie. Do zrobienia tego używa się wskaźników.

Przypisanie dynamicznej alokacji tablicy.

         Kolejnym krokiem jest zainicjowanie generatora liczb losowych oraz wypełnienie nimi tablicy. Do generacji używamy komendy srand().  Następnie musimy przepisać wartości z pierwszej tablicy do dwóch pozostałych, tak żeby dane wszędzie były jednakowe. 

Zainicjowanie generatora liczb losowych.


        Kolejnym etapem jest wywołanie napisów na ekran, rozpoczęcie odliczania zegara, wywołanie funkcji sortowania, zatrzymanie czasu zegara, obliczenie wartości czasu sortowania i wypisania go na ekran. Należy powtórzyć te czynności przy każdym sortowaniu.

         Na koniec należy zwolnić pamięć, którą przydzieliliśmy dynamicznie. Wykorzystuje się do tego operatora „delete”. Musimy pamiętać także o nawiasie kwadratowym, ponieważ nasz wskaźnik był tablicą rekordów. Po tej operacji kończymy program operatorem „return 0”, oraz zamykając nawias funkcji głównej.



        Sortowanie przez wstawianie należy również do prostych, tak samo jak sortowanie przez wybór. Różni się jedynie metodą wykonania, a mianowicie następne elementy z uporządkowanej tablicy są wycinane i wstawiane we właściwe miejsce dodatkowej posortowanej już listy. 
        Metoda polega na sprawdzaniu sąsiadujących obok siebie cyfr. Pierwszy element porównywany jest z drugim, jeżeli liczba jest większa, wstawiana jest na początek. Następnie sprawdzany jest element trzeci, który porównywany jest z dwoma poprzednimi, dalej czwarty, zestawiany z trzema początkowymi, itd.

Specyfikacja problemu sortowania przez wstawianie.


Lista kroków przedstawiająca rozwiązanie algorytmu sortowania przez wybór.


Schemat blokowy zawierający algorytm sortowania przez wstawianie.


W podanym przypadku sortowanie rozpoczynamy od końca listy, dlatego zmienną j będziemy zmniejszać. Ze wszystkich elementów zostaje wybierany jeden, następnie umieszczamy go w naszej zmiennej pomocniczej a.  Pętla zewnętrzna zajmuje się ustawianiem miejsc od ostatniego do pierwszego, natomiast pętla wewnętrzna szuka uporządkowania dla podanych wartości w tablicy oraz ustawia je w tej tablicy tak, by wartości były posortowane. Gdy pętla zewnętrzna przebiegnie wszystkie elementy o indeksach od ostatniego do pierwszego, tablica będzie posortowana. 

Program sortujący dane metodą sortowania przez wstawianie.








Sortowanie przez wybór jest metodą najprostszą z sortowania. W tablicy należy znaleźć najmniejszy element i zamienić go miejscem z pierwszym elementem tablicy. Jeżeli najmniejszy element występuje wielokrotnie to trzeba wziąć pod uwagę ten, który znajduje się najbliżej początku tablicy. 
Następnie we fragmencie tablicy, który obejmuje elementy od drugiego do ostatniego poszukiwane jest minimum i należy zamienić je miejscem z drugim elementem tablicy. Należy tak postępować dodając za każdym razem element do posortowanej części aż nastąpi ostatni element tablicy.
Podany problem sortowania przez wybór można przedstawić w kilku rozwiązaniach. Zaczynamy od specyfikacji problemu, która wyjaśni, jakie dane mamy, jakich potrzebujemy oraz jakich pomocniczych zmiennych będziemy używać. 

Specyfikacja problemu sortowania przez wybór.


Lista kroków przedstawiająca rozwiązanie algorytmu sortowania przez wybór.


Schemat blokowy zawierający algorytm sortowania przez wybór.

Schemat blokowy zawiera dwie pętle sterujące wartościami i oraz j. Zewnętrzna steruje wartością zmiennej j, która wyznacza elementy zbioru od 1 do k-1. Algorytm ustawia element najmniejszy jako pierwszy element zbioru. Druga pętla (wewnętrzna) steruje zmienną i oraz porównuje resztę elementów z wartością minimalną. Pętla będzie sprawdzać czy element zbioru t[i] jest mniejszy od elementu t[pmin]. Jeżeli tak to znaleziony został nowy element minimalny. Kiedy pętla wewnętrzna zakończy swoje działanie wartość pmin będzie zawierać indeks elementu minimalnego. Następnie algorytm zamieni miejscami element t[j] z t[pmin], dzięki temu element minimalny znajdzie się w tej pozycji, której powinien. Zwiększając wartość j algorytm przechodzi do następnego elementu zbioru, wykonuje pętlę zewnętrzną.

Program sortujący dane zawarte w tablicy 10-cio elementowej metodą przez wybór.







Algorytm szybkiego sortowania stosuje się najczęściej w programach i jest on najważniejszym sposobem sortowania. Jest również trudniejszy i wykorzystywany w większych bazach danych. Cechuje się niezmierną szybkością wykonania, dzieleniem danego problemu na mniejsze i rozwiązywanie ich następuje rekurencyjnie, wszystkie rozwiązane podproblemy łączą się ze sobą tworząc pełne rozwiązanie. Rekurencja, inaczej rekursja to sytuacja, kiedy funkcja odwołuje się do samej siebie. Tworzy ona swoje kopie aż do napotkania momentu, 
w którym funkcja może już wyznaczyć wynik.
 Mottem szybkiego sortowania jest dziel i zwyciężaj, które jest jednoznaczne do tego by ułatwić programowanie szybszym i sprytniejszym sposobem. Jeżeli trudno jest posortować dużą tablicę, dzielona jest ona na mniejsze, takie, które jest szybko uporządkować, do momentu aż nie zostanie już nic do sortowania.
Przy tym typie sortowania, na początek wybierana jest oś, czyli losowa liczba z tablicy, która jest linią podziału listy na dwie mniejsze. Liczby mniejsze od osi ustawiane są na lewo tablicy, natomiast większe na prawo. Zostają stworzone dwie tablice do posortowania. Kolejnym krokiem jest wyznaczenie następnych osi tych dwóch list oraz ustawienie liczb według podanego wcześniej schematu. Pojawiają się tym sposobem coraz mniejsze tablice, a także liczby w kolejności uporządkowanej. 
Do oddzielenia liczb mniejszych na lewo, większych na prawo komputer posłuży się algorytmem partycjonującym, czyli takim, który podzieli dany zbiór na podzbiory według jakiegoś kryterium.

Specyfikacja problemu szybkiego sortowania.
Lista kroków sortowania szybkiego.



Program sortujący tablicę danych za pomocą sortowania szybkiego.



Sortowanie bąbelkowe należy do metod dość instynktownych jednak jest to metoda bardzo wolna.
Polega ona na porównywaniu dwóch następnych elementów w tablicy i zamianie ich zgodnie z zasadą taką, że jeżeli wykonujemy sortowanie rosnące, to liczba mniejsza zostaje zamieniona na początek, a jeśli jest to sortowanie malejące, to liczba większa zapisana jest na przodzie. Porównywanie elementów rozpoczynane jest od tyłu tablicy. Po jednym przejściu listy należy powtórzyć czynność tyle razy ile liczb w tablicy.
Lista kroków przedstawiająca rozwiązanie algorytmu sortowania bąbelkowego.

K01: Dla j = 1,2,...,k - 1: wykonuj K02
K02: Dla i = 1,2,...,k - 1: jeśli t[i] > t[i + 1], to t[i] ↔ t[i + 1]
K03: Zakończ
 Schemat blokowy sortowania bąbelkowego
 
                                                                             

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 k - 1 razy. Wewnątrz pętli nr 1 umieszczona jest pętla nr 2 sterowana przez zmienną i. Wykonuje się również k - 1 razy. 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.

Implementacja kodu źródłowego programu sortującego dane metodą sortowania bąbelkowego.




Sortowanie zbioru danych

Sortowaniem, zwanym również porządkowaniem, nazywamy proces układania elementów zbioru według ściśle określonych zasad logicznych. Zbiór posortowany charakteryzuje porządek, a elementy tego zbioru są ustawione w kolejności określonej relacją porządkowania. W oparciu relacje każdy zbiór elementów można posortować:

  •  rosnąco — element poprzedni zbioru jest nie większy niż element następny, na przykład {1, 2, 5, 5, 7},

  • malejąco — element poprzedni jest nie mniejszy niż element następny zbioru, na przykład {8, 4, 4, 3, 2}.



Sortowanie jest procesem ułożenia informacji w zadanej kolejności. Kiedy ilość danych jest mała lub sortowanie przydatne jest nieczęsto, stosuje się algorytmy sortowania o prostej implementacji. Jednak do sortowaniu dużej ilości danych, przy dużych projektach stosuje się algorytmy bardziej złożone, które mają za zadanie wykonać polecenia szybko oraz efektownie. Warto wziąć pod uwagę też to, że sortowanie wykona się szybciej, jeżeli tablica będzie już w jakiejś części uporządkowana. Sortowanie jest przydatne w celu organizacji pracy, a także szybkim odszukiwaniu danych. Ułatwia korzystanie z informacji, jest idealną metodą na zaoszczędzenie czasu.
Strona główna

Archiwum

  • ▼  2018 (9)
    • ▼  lutego (9)
      • Zestaw instrukcji laboratoryjnych do pobrania
      • Złożoność algorytmów sortujących
      • Sortowanie przez wstawianie
      • Sortowanie przez wybór
      • Sortowanie szybkie
      • Sortowanie bąbelkowe
      • O programowaniu w życiu codziennym oraz trochę his...
      • Programowanie strukturalne i obiektowe w języku C++
      • Co to jest sortowanie?

Lista polecanych artykułów

Copyright © 2016 Programowanie C++. Created by OddThemes & Free Wordpress Themes 2018