#include <iostream>
#include <cassert>
#include <vector>
#include <time>
#include <windows>
using namespace std;
//QUICKSORT
template<class T>
int partition(T &array, int top, int bottom)
{
int x = array[top];
int i = top - 1;
int j = bottom + 1;
int temp;
int a = 0;
do
{
do
{
j--;
}while (x >array[j]);
do
{
i++;
} while (x <array[i]);
if (i < j)
{
temp = array[i]; // switch elements at positions i and j
array[i] = array[j];
array[j] = temp;
a++;
}
}while (i < j);
return j; // returns middle index
}
template<class T>
void quicksort(T &array, int top, int bottom)
{
// top = subscript of beginning of vector being considered
// bottom = subscript of end of vector being considered
// this process uses recursion - the process of calling itself
int middle;
if (top < bottom)
{
middle = partition(array, top, bottom);
quicksort(array, top, middle); // sort top partition
quicksort(array, middle+1, bottom); // sort bottom partition
}
return;
}
//END: QUICKSORT
//BOUBBLESORT
template<class T>
void bubble_sort(T &array, int sz)
{
int i, j, flag = 1; // set flag to 1 to begin initial pass
int temp; // holding variable
int arrayLength = sz;
int b = 0;
for(i = 1; (i <= arrayLength) && flag; i++)
{
flag = 0;
for (j=0; j < (arrayLength -1); j++)
{
if (array[j+1] > array[j]) // ascending order simply changes to <
{
temp = array[j]; // swap elements
array[j] = array[j+1];
array[j+1] = temp;
flag = 1; // indicates that a swap occurred.
b++;
}
}
}
return; //arrays are passed to functions by address; nothing is returned
}
//END: BOUBBLESORT
//EXCHANGESORT
template <class T>
void exchange_sort(T &array, int sz)
{
int i, j;
int temp; // holding variable
int arrayLength = sz;
int c = 0;
for (i=0; i< (arrayLength -1); i++) // to represent element to be compared
{
for(j = (i+1); j < arrayLength; j++) // to represent the rest of the elements
{
if (array[i] < array[j])
{
temp= array[i]; // swap
array[i] = array[j];
array[j] = temp;
c++;
}
}
}
return;
}
//END: EXCHANGESORT
//SELECTIONSORT
template <class T>
void selection_sort(T &array, int sz)
{
int i, j, first, temp;
int array_size = sz;
int d = 0;
for (i= array_size - 1; i > 0; i--)
{
first = 0; // initialize first to the subscript of the first element
for (j=1; j<=i; j++) //Find smallest element between the positions 1 and i.
{
if (array[j] < array[first])
first = j;
d++;
}
temp = array[first]; // Swap smallest element found with one in position i.
array[first] = array[i];
array[i] = temp;
}
return;
}
//END: SELECTIONSORT
//INSERTIONSORT
template <class T>
void insertion_sort(T &array, int sz)
{
int i, j, key, array_length=sz;
int e = 0;
for(j = 1; j < array_length; j++) //Notice starting with 1 (not 0)
{
key = array[j];
for(i = j - 1; (i >= 0) && (array[i] < key); i--) //Move smaller values up one position
{
array[i+1] = array[i];
e++;
}
array[i+1] = key; //Insert key into proper position
}
return;
}
//END: INSERTIONSORT
//SHELLSORT
template <class T>
void shell_sort(T &array, int sz)
{
int flag = 1, d = sz, i, temp, arrayLength = sz;
int f = 0;
while( flag || (d>1)) // boolean flag (true when not equal to 0)
{
flag = 0; // reset flag to 0 to check for future swaps
d = (d+1) / 2;
for (i = 0; i < (arrayLength - d); i++)
{
if (array[i + d] > array[i])
{
temp = array[i + d]; // swap items at positions i+d and d
array[i + d] = array[i];
array[i] = temp;
flag = 1; // indicate that a swap has occurred
f++;
}
}
}
return;
}
//END: SHELLSORT
template <class T>
void printArray(T ar[], int sz)
// prints array ar of size sz
{
for(int i=0; i<sz; i++)
cout << ar[i] << "\t";
cout << endl;
} // end printArray() ////////////////
int main(int argc, char *argv[])
{int T[10];
int i, a, b, c, d, e, f;
for(i=0;i<10;i++)
{ printf("podaj liczbe: ");
scanf("%d", &T[i]);
}
int SIZE = T[10];
vector<int> v(SIZE);
vector<int> temp;
srand(time(0));
for(int i=0; i<SIZE; i++)
v[i]=rand()%SIZE+1;
temp=v;
// printArray(v.begin(), SIZE);
// quicksort(v, 0, 7);
// shell_sort(v, SIZE);
// printArray(v.begin(), 8);
// printArray(temp.begin(), 8);
double start, end;
start = GetTickCount();
quicksort(v, 0, SIZE - 1);
end = GetTickCount();
cout<<"Quick Sort: "<<(end-start)<<" ms"<<"\n";
printf("Step: %d", a);
v=temp;
start = GetTickCount();
bubble_sort(v, SIZE);
end = GetTickCount();
cout<<"Bubble Sort: "<<(end-start)<<" ms"<<"\n";
printf("Step: %d", b);
v=temp;
start = GetTickCount();
exchange_sort(v, SIZE);
end = GetTickCount();
cout<<"Exchange Sort: "<<(end-start)<<" ms"<<"\n";
printf("Step: %d", c);
v=temp;
start = GetTickCount();
selection_sort(v, SIZE);
end = GetTickCount();
cout<<"Selection Sort: "<<(end-start)<<" ms"<<"\n";
printf("Step: %d", d);
v=temp;
start = GetTickCount();
insertion_sort(v, SIZE);
end = GetTickCount();
cout<<"Insertion Sort: "<<(end-start)<<" ms"<<"\n";
printf("Step: %d", e);
v=temp;
start = GetTickCount();
shell_sort(v, SIZE);
end = GetTickCount();
cout<<"Shell Sort: "<<(end-start)<<" ms"<<"\n";
printf("Step: %d", f);
cin.get();
return (0);
} // end main()
https://www.elektroda.pl/rtvforum/faq.php
) ale przy kończeniu wysypuje się na zwalnianiu pamięci.
)
