Porównanie prędkości działania algorytmów sortujacyc Witam utknalem troche w miejscu .Przy uruchomieniu program pyta jak dużo elementów ma mieć tablica, następnie użytkownik podaje np 50000 i program tworzy 5 tablic o takiej ilości elementów, które następnie zapełnia takimi samymi losowymi liczbami.
Następnie program ma posortować te tablice, które są wypełnione tymi samymi liczbami i na końcu program ma podać czasy sortowań dla poszczególnych algorytmów.
To mój kod:
#include <iostream>
#include <windows.h>
#include <ctime>
#include <stdio.h>
#include <string>
#include <algorithm>
using namespace std;
void bubbleSort(int *tabBubbleSort, int tabElements)
{
int i, j;
for (i = 0; i < tabElements - 1; i++)
for (j = 0; j < tabElements - i - 1; j++)
if (tabBubbleSort[j] > tabBubbleSort[j + 1])
swap(tabBubbleSort[j], tabBubbleSort[j + 1]);
}
void QuickSort( int *tabQuickSort, int left, int right )
{
int i = left;
int j = right;
int x = tabQuickSort[( left + right ) / 2 ];
do
{
while( tabQuickSort[ i ] < x )
i++;
while( tabQuickSort[ j ] > x )
j--;
if( i <= j )
{
swap( tabQuickSort[ i ], tabQuickSort[ j ] );
i++;
j--;
}
}
while( i <= j );
if( left < j ) QuickSort( tabQuickSort, left, j );
if( right > i ) QuickSort( tabQuickSort, i, right );
}
int *pom;
void MergeSort(int *tabMergeSort, int lewy, int srodek, int prawy)
{
int i, j;
for(i = srodek + 1; i>lewy; i--)
{
pom[i-1] = tabMergeSort[i-1];
for(j = srodek; j<prawy; j++)
pom[prawy+srodek-j] = tabMergeSort[j+1];
for(int k=lewy; k<=prawy; k++)
if(pom[j]<pom[i])
tabMergeSort[k] = pom[j--];
else
tabMergeSort[k] = pom[i++];
}
}
void SeletcionSort( int *tabSeletcionSort, int tabElements )
{
int k;
for( int i = 0; i < tabElements; i++ )
{
k = i;
for( int j = i + 1; j < tabElements; j++ )
if( tabSeletcionSort[ j ] < tabSeletcionSort[ k ] )
k = j;
swap( tabSeletcionSort[ k ], tabSeletcionSort[ i ] );
}
}
void InsertionSort( int *tabInsertionSort, int tabElements)
{
int temp, j;
for( int i = 1; i < tabElements; i++ )
{
temp = tabInsertionSort[ i ];
for( j = i - 1; j >= 0 && tabInsertionSort[ j ] > temp; j-- )
tabInsertionSort [j + 1 ] = tabInsertionSort[ j ];
tabInsertionSort[ j + 1 ] = temp;
}
}
int main()
{
int tabElements;
int *tabBubbleSort, *tabQuickSort, *tabMergeSort, *tabSeletcionSort, *tabInsertionSort;
clock_t start, stop;
srand (time(NULL));
cout << "Give numer of elements: " << endl;
cin >> tabElements;
tabBubbleSort = new int[tabElements];
tabQuickSort = new int[tabElements];
tabMergeSort = new int[tabElements];
tabSeletcionSort = new int[tabElements];
tabInsertionSort = new int[tabElements];
populateTables (tabBubbleSort, tabQuickSort, tabMergeSort, tabSeletcionSort, tabInsertionSort, tabElements);
start = clock();
quickSort(tabQuickSort, 0, tabElements-1);
stop = clock ();
start = clock();
bubbleSort(tabBubbleSort, tabElements);
stop = clock ();
cout << "BubbleSort status: " << isSortedAsc(tabBubbleSort,tabElements) << endl;
cout << "Bubble took " << caculateTime(start, stop) << "seconds" << endl;
cout << "QuickSort status: " << isSortedAsc(tabBubbleSort,tabElements) << endl;
cout << "QuickSort took " << caculateTime(start, stop) << "seconds" << endl;
start = clock();
mergeSort(tabMergeSort, 0, tabElements-1);
stop = clock ();
cout << "MergeSort status: " << isSortedAsc(tabBubbleSort,tabElements) << endl;
cout << "MergeSort took " << caculateTime(start, stop) << "seconds" << endl;
start = clock();
selectionSort(tabSeletcionSort, tabElements);
stop = clock ();
cout << "SeletcionSort status: " << isSortedAsc(tabBubbleSort,tabElements) << endl;
cout << "SeletcionSort took " << caculateTime(start, stop) << "seconds" << endl;
start = clock();
insertionSort(tabInsertionSort, tabElements);
stop = clock ();
cout << "InsertionSort status: " << isSortedAsc(tabBubbleSort,tabElements) << endl;
cout << "InsertionSort took " << caculateTime(start, stop) << "seconds" << endl;
delete [] tabBubbleSort;
tabBubbleSort = NULL;
delete [] tabQuickSort;
tabQuickSort = NULL;
delete [] tabMergeSort;
tabMergeSort = NULL;
delete [] tabSeletcionSort;
tabSeletcionSort = NULL;
delete [] tabInsertionSort;
tabInsertionSort = NULL;
return 0;
}