P

ROJEKT 

1

 

-

 

Z

AŁOŻENIA

 

 

 

KRÓTKI OPIS ZADANIA 

 

Projekt  1  przewiduje  porównanie  efektywności  działania  dwóch  wybranych  algorytmów  sortowania. 

Pierwszym  zadaniem  jest  napisanie  w  języku  C++  dwóch  programów  –  testowego  oraz  głównego,  który 
posłuży  do  właściwego  zbadania  wspomnianych  algorytmów.  Drugim  zadaniem  jest  wykonanie 
podsumowującego sprawozdania. 

PROGRAMY 

PROGRAM 1 - TESTOWY 

1.

  Tworzymy  plik  tekstowy  o  nazwie  DaneTestowe.txt,  w  którym  umieszczamy  liczbę  n  elementów  (liczb 

naturalnych) przeznaczonych do sortowania, a następne wartości tych liczb. 

2.

  Wczytujemy dane z pliku DaneTestowe.txt do programu. Elementy, które będą sortowane wstawiamy do 

tablicy dynamicznej o długości n. Sortujemy elementy wykorzystując do tego celu dwa zadane algorytmy 
sortowania. Elementy tablicy przed sortowaniem oraz po sortowaniu każdą z metod wypisujemy na ekran. 

PROGRAM 2 – GŁÓWNY (PORÓWNANIE ALGORYTMÓW SORTOWANIA) 

Zadaniem  Programu  2  jest  porównanie  dwóch  wybranych  algorytmów  sortowania  ze  względu  na  czas 
(w sekundach) potrzebny na ułożenie elementów w kolejności rosnącej w zależności od liczby elementów oraz 
kolejności  ich  ułożenia.  Na  potrzeby  każdego  z  opisanych  w  Tabeli  (zob.  sprawozdanie)  przypadków 
generujemy  zbiór  danych  testowych  wybierając  taką  liczbę  elementów  n,  dla  której  najlepiej  widać  różnice 
pomiędzy  algorytmami,  a  następnie  sprawdzamy  czasy  działania  procedur.  Wszystkie  zbiory  danych 
wejściowych  generujemy  automatycznie  do  odpowiednich  plików  tekstowych  (DanePrzypadek1.txt, 
DanePrzypadek2.txt

  oraz  DanePrzypadek3.txt)  i  odczytujemy  w  programie.  Do  utworzenia  zbioru  danych 

testowych w Przypadku 1 możemy posłużyć się losowym generowaniem liczb w języku C++. 

UWAGI 

1.

  W programach używamy wyłącznie tablic dynamicznych o rozmiarze zależnym od n. 

2.

  Algorytmy  sortowania  realizujemy  w  dwóch  osobnych  funkcjach,  do  których  przekazujemy  liczbę  n 

elementów tablicy oraz tablicę elementów. 

3.

  Po zakończeniu działania funkcji posortowane elementy tablicy dostępne są w programie. 

ALGORYTMY SORTOWANIA 

1.

  Sortowanie przez proste wstawianie. 

2.

  Sortowanie przez wstawianie połówkowe. 

3.

  Sortowanie przez proste wybieranie. 

4.

  Sortowanie przez prostą zamianę (sortowanie bąbelkowe). 

5.

  Sortowanie mieszane. 

6.

  Sortowanie Stella. 

7.

  Sortowanie przez kopcowanie. 

8.

  Sortowanie szybkie. 

9.

  Sortowanie szybkie – wersja rekurencyjna.