Sprawozdanie.docx

Sprawozdanie – algorytmy sortujące

10.12.2012r.

Mateusz Kaczmarczyk

Jakub Jóźwiak

Celem tego sprawozdania jest przetestowanie szybkości działania 4 algorytmów sortujących w zależności od liczby i rodzaju danych do posortowania:

BubbleSort (sortowanie bąbelkowe)

InsertionSort (sortownie przez wstawianie)

MergeSort (sortowanie przez scalanie)

QuickSort (sortowanie szybkie).

Platforma testowa

Komputer o następujących parametrach:

·         procesor Intel Core i5 (2x2,3GHz)

·         4GB pamięci RAM

·         64-bitowy system operacyjny Windows 7 Home Premium

·         Visual Studio Professional 2012

Napisany przez nas program testujący algorytmy sortowania dokonuje wszystkich pomiarów podczas 1 uruchomienia. Wyniki zawierające informacje o czasach wykonywania 4 algorytmów sortujących (dla różnych typów i ilości danych) zapisywane są do plików tekstowych. Po zakończeniu każdego z sortowań automatycznie otwierany jest plik z wynikami.

Test wykonaliśmy dla 4 typów danych:

1.       Losowe liczby z zakresu [0,1000]

2.       Posortowane liczby z zakresu [0,1000]

3.       Odwrotnie posortowane liczby z zakresu [0,1000]

4.       Losowe liczby z zakresu [0,1]

Oraz dla następujących ilości danych:

1k, 2k, 4k, 8k, 16k, 32k, 64k, 128k, 256k, 512k.

Dla MergeSort i QuickSort dodatkowo sprawdziliśmy działanie algorytmów dla: 256k, 512k, 1024k i 2048k liczb, ponieważ dla mniejszych ilości wykonywały się one w czasie poniżej 16ms, co uniemożliwiało zbadanie zależności czasu od ilości danych.

k=1024 elementy.

Wyniki pomiarów przedstawiamy w postaci tabeli oraz wykresów.

BubbleSort – sortowanie bąbelkowe

k = 1024 elementy

Wszystkie czasy sortowania podane w milisekundach.

BubbleSort to prosta metoda sortowania o średniej (i jednocześnie pesymistycznej) złożoności czasowej O(n2). W przypadku optymistycznym (dane już posortowane) złożoność wyniesie O(n), ponieważ algorytm przejdzie przez tablicę tylko raz - dzięki fladze, która sprawdza czy elementy zostały chociaż raz zamienione.

Algorytm BubbleSort nie wymaga dodatkowej pamięci i jest bardzo prosty w implementacji. Jego wadą jest niska wydajność dla większej liczby elementów.

Złożoność:

·         Typowa : O(n2)

·         Pesymistyczna: O(n2)

·         Optymistyczna O(n)

InsertionSort – sortowanie przez wstawianie