Porównanie prędkości działania algorytmów sortujacych

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;
}

1. nie podałeś jaki jest problem;
2. brak definicji funkcji populateTables;
3. 5000 elementów od użytkownika? Prędzej zwariuje, rób losowe.
4. Przy losowych możesz zapamiętać seed wygenerować ciąg liczb, odtworzyć seed i znowu wygenerować będzie dokładnie taki sam.
5. Stwórz opakowania dla quick i merge aby można było wywołać: quickSort(tabSort,tabElements); wtedy można stworzyć i użyć tablicę funkcji.

Dla quickSort np tak :

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>

template<typename Iter>
void quickSort( Iter left,Iter right)
{
    auto size = std::distance(left, right);
    if (size <= 1)
    {
        return;
    }
    auto pivot = std::next(right, -1);
    if (size == 2 && *pivot < *left)
    {
        std::iter_swap(left, pivot);
    }
    auto wall = left;
    auto curr = left;

    while (curr != right)
    {
        if (*curr < *pivot)
        {
            std::iter_swap(wall, curr);
            wall++;
        }
        curr++;
    }

    std::iter_swap(pivot, wall);
    quickSort(left, wall);
    quickSort(wall + 1, right);
}

int main()
{
    std::srand(unsigned(std::time(nullptr)));
    std::vector<int> myVec(15);
    std::generate(myVec.begin(), myVec.end(), std::rand);
    quickSort(myVec.begin(), myVec.end());
    for (const auto& item : myVec)
    {
        std::cout << item << std::endl;
    }
    return 0;
}

Program wkoncu sie uruchomil tylko sie wysypuje jak chce wieksze liczby posortowac przez scalanie, wybieranie i wstawianie

```#include <iostream>
#include <ctime>
#include <time.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <iterator>
#include <numeric>
using namespace std;

void populateTables(int*tabBubbleSort,int *tabQuickSort,int *tabMergeSort,int *tabSeletcionSort,int *tabInsertionSort,int tabElements)
{

    srand(time(NULL));
    for (int i = 0; i < tabElements; i++)
    {
        tabBubbleSort[i] = rand () % 1000000 +1 ;
        tabQuickSort[i] = tabBubbleSort[i];
        tabMergeSort[i] = tabQuickSort[i];
        tabSeletcionSort[i] = tabMergeSort[i];
        tabInsertionSort[i] = tabSeletcionSort[i];
    }
}


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 );

}

void merging(int *tabMergeSort, int start, int srodek, int koniec)
{
    int *tab_pom = new int[(koniec-start)];
    int i = start, j = srodek+1, k = 0;

    while (i <= srodek && j <= koniec)
    {
        if (tabMergeSort[j] < tabMergeSort[i])
        {
            tab_pom[k] = tabMergeSort[j];
            j++;
        }
        else
        {
            tab_pom[k] = tabMergeSort[i];
            i++;
        }
        k++;
    }

    if (i <= srodek)
    {
        while (i <= srodek)
        {
            tab_pom[k] = tabMergeSort[i];
            i++;
            k++;
        }
    }
    else
    {
        while (j <= koniec)
        {
            tab_pom[k] = tabMergeSort[j];
            j++;
            k++;
        }
    }

    for (i = 0; i <= koniec-start; i++)
        tabMergeSort[start+i] = tab_pom[i];

}

void mergeSort(int *tabMergeSort, int start, int koniec)
{
    int srodek;

    if (start != koniec)
    {
        srodek = (start + koniec)/2;
        mergeSort(tabMergeSort, start, srodek);
        mergeSort(tabMergeSort, srodek+1, koniec);
        merging(tabMergeSort, start, srodek, koniec);
    }
}
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()
{
    clock_t start, stop;
    int time;
    int tabElements;
    int *tabBubbleSort, *tabQuickSort, *tabMergeSort, *tabSeletcionSort, *tabInsertionSort;



    cout << "Give number 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();
    bubbleSort(tabBubbleSort, tabElements);
    time = (double )(stop - start) / CLOCKS_PER_SEC;

    cout << "time required to bubble-sort: "<< time << " s" << endl;

    start = clock();
    quickSort(tabQuickSort, 0, tabElements-1);
    stop = clock ();
    time = (double) (stop - start) / CLOCKS_PER_SEC;


    cout << "time required to quick-sort: "<< time << " s" << endl;

    start = clock();
    mergeSort (tabMergeSort, 0, tabElements - 1);
    stop = clock ();
    time = ( double) (stop - start) / CLOCKS_PER_SEC;

    cout << "time required to merge-sort: " << time << " s" << endl;

    start = clock();
    seletcionSort(tabSeletcionSort, tabElements);
    stop = clock ();
    time = (double) (stop - start) / CLOCKS_PER_SEC;

    cout << "time required to selection-sort: " <<  time << " s" << endl;

    start = clock();
    insertionSort(tabInsertionSort, tabElements);
    stop = clock ();
    time = (double) (stop - start) / CLOCKS_PER_SEC;

    cout << "time required to insertion-sort: " <<  time << " s" << endl;

    delete [] tabBubbleSort;
    tabBubbleSort = NULL;
    delete [] tabQuickSort;
    tabQuickSort = NULL;
    delete [] tabMergeSort;
    tabMergeSort = NULL;
    delete [] tabSeletcionSort;
    tabSeletcionSort = NULL;
    delete [] tabInsertionSort;
    tabInsertionSort = NULL;


    return 0;
}

Za dużo pamięci wymagasz, w poprzednim poście dałem rozwiązanie.

Widzę w funkcji merging:

int *tab_pom = new int[(koniec-start)];

Ale nie widać delete.

Tutaj znowu nie widać stop:

    start = clock();
    bubbleSort(tabBubbleSort, tabElements);
    time = (double )(stop - start) / CLOCKS_PER_SEC;

#include <ctime>
#include <cstdlib>
#include <vector>
#include <iostream>
using namespace std;

using algo=void(vector<int> &data,size_t count);

void nothing(vector<int> &data,size_t count) {}
void add(vector<int> &data,size_t count) { for(int &value:data) value+=1; }
void mul(vector<int> &data,size_t count) { for(int &value:data) value*=2; }

struct TestNode { const char *title; algo *fun; } tests[]
{
	{"Call NOTHING",&nothing},
	{"Call ADD",&add},
	{"Call MUL",&mul},
};

void show(vector<int> &data,size_t count)
{
	for(int &value:data) cout<<value<<' ';
	cout<<endl;
}

double checktime(unsigned long seed,size_t count,algo *fun)
{
	vector<int> data(count);
	srand(seed);
	for(int &value:data) value=1+rand()%1000000;
	clock_t start=clock();
    fun(data,count);
    double seconds=1.0*(clock()-start)/CLOCKS_PER_SEC;
    show(data,count); // np. check
    return seconds;
}

int main()
{
	unsigned long seed=time(0);
	for(size_t count;(cout<<"Podaj rozmiar: ")&&(cin>>count)&&(count>1);)
	{
		for(const TestNode &test:tests)
		{
			double seconds=checktime(seed,count,test.fun);
			cout<<test.title<<" "<<seconds<<" sec."<<endl<<endl;
		}
		seed=rand();
	}
	return 0;
}

WKoncy działa, problem byl z algorytmem scalajacym

```#include <iostream>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <iostream>
using namespace std;

void populateTables(int*tabBubbleSort,int *tabQuickSort,int *tabMergeSort,int *tabSeletcionSort,int *tabInsertionSort,int tabElements)
{

    srand(time(NULL));
    for (int i = 0; i < tabElements; i++)
    {
        tabBubbleSort[i] = rand () % 10000 +1 ;
        tabQuickSort[i] = tabBubbleSort[i];
        tabMergeSort[i] = tabQuickSort[i];
        tabSeletcionSort[i] = tabMergeSort[i];
        tabInsertionSort[i] = tabSeletcionSort[i];
    }
}


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 );

}

void scalanie(int tabMergeSort[], int start, int srodek, int koniec)
{

    int *tab_pom = new int[(koniec-start+1)]; // utworzenie tablicy pomocniczej
    int i = start, j = srodek+1, k = 0; // zmienne pomocnicze

    while (i <= srodek && j <= koniec)
    {
        if (tabMergeSort[j] < tabMergeSort[i])
        {
            tab_pom[k] = tabMergeSort[j];
            j++;
        }
        else
        {
            tab_pom[k] = tabMergeSort[i];
            i++;
        }
        k++;
    }

    if (i <= srodek)
    {
        while (i <= srodek)
        {
            tab_pom[k] = tabMergeSort[i];
            i++;
            k++;
        }
    }
    else
    {
        while (j <= koniec)
        {
            tab_pom[k] = tabMergeSort[j];
            j++;
            k++;
        }
    }

    for (i = 0; i <= koniec-start; i++)
        tabMergeSort[start+i] = tab_pom[i];

    delete [] tab_pom;
}

void mergeSort(int tabMergeSort[], int start, int koniec)
{

    int srodek;

    if (start != koniec)
    {
        srodek = (start + koniec)/2;
        mergeSort(tabMergeSort, start, srodek);
        mergeSort(tabMergeSort, srodek+1, koniec);
        scalanie(tabMergeSort, start, srodek, koniec);
    }
}
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()
{
    clock_t start, stop;
    int  time;
    int tabElements;
    int *tabBubbleSort, *tabQuickSort, *tabMergeSort, *tabSeletcionSort, *tabInsertionSort;



    cout << "Give number 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();
    bubbleSort(tabBubbleSort, tabElements);
    stop = clock ();
    time = (double )(stop - start) / CLOCKS_PER_SEC;

    cout << "time required to bubble-sort: "<< time << " s" << endl;

    start = clock();
    quickSort(tabQuickSort, 0, tabElements-1);
    stop = clock ();
    time = (double) (stop - start) / CLOCKS_PER_SEC;


    cout << "time required to quick-sort: "<< time << " s" << endl;

    start = clock();
    mergeSort (tabMergeSort, 0, tabElements - 1);
    stop = clock ();
    time = ( double) (stop - start) / CLOCKS_PER_SEC;

    cout << "time required to merge-sort: " << time << " s" << endl;

    start = clock();
    seletcionSort(tabSeletcionSort, tabElements);
    stop = clock ();
    time = (double) (stop - start) / CLOCKS_PER_SEC;

    cout << "time required to selection-sort: " <<  time << " s" << endl;

    start = clock();
    insertionSort(tabInsertionSort, tabElements);
    stop = clock ();
    time = (double) (stop - start) / CLOCKS_PER_SEC;

    cout << "time required to insertion-sort: " <<  time << " s" << endl;

    delete [] tabBubbleSort;
    tabBubbleSort = NULL;
    delete [] tabQuickSort;
    tabQuickSort = NULL;
    delete [] tabMergeSort;
    tabMergeSort = NULL;
    delete [] tabSeletcionSort;
    tabSeletcionSort = NULL;
    delete [] tabInsertionSort;
    tabInsertionSort = NULL;


    return 0;
}