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.