Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <sstream>
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include <time.h>
- #include <fstream>
- #include <conio.h>
- using namespace std;
- clock_t start, stop;
- long long int compares, switches;
- const int genMin=0;
- const int genMax=10;
- int arraySize=100000;
- const bool print = 0;
- const int tests=10;
- bool keyb=0;
- bool error=0;
- //int numbers[10];
- fstream file;
- int isNumber(string thing){
- for(int i=0; i<thing.length(); i++){
- if(thing[i]!@=45 && (thing[i]<48 || thing[i]>57))
- return 0;
- }
- return 1;
- }
- int checkFile(){
- string nr;
- if(!file.good()){
- cout<<"Brak pliku data.txt"<<endl;
- return 0;
- }
- for(int i=0; true; i++){
- file >> nr;
- //fscanf(file, "%s\n", &nr);
- //printf("%d %s ", i+1, nr);
- //cout<<nr<<" : "<<isNumber(nr)<<endl;
- if(file.eof()){
- //cout<<"h"<<endl;
- return i;
- }
- if(!isNumber(nr)){
- //cout<<nr<<endl;
- return 0;
- }
- }
- }
- void loadFile(int tab[]){
- int fileSize=checkFile();
- //cout<<fileSize<<endl;
- if(fileSize){
- //fclose(file);
- fstream f;
- f.open("data.txt");
- for(int i=0; i<arraySize; i++){
- f >> tab[i];
- //fscanf(f, "%d\n", &numbers[i]);
- }
- //fclose(f);
- }else{
- error++;
- cout<<"dane nieprawidlowe"<<endl;
- }
- }
- void keyboard(int tab[]){
- for (int i = 0; i < arraySize; i++) {
- string z;
- cin>>z;
- if (isNumber(z)==1){
- stringstream geek(z);
- int x ;
- geek >> x;
- tab[i]=x;
- }else{
- error++;
- printf("Niepoprawna wartosc wprowadzona");
- break;
- }
- }
- }
- void swapp(int* a, int* b){
- switches++;
- int t = *a;
- *a = *b;
- *b = t;
- }
- void generateArray(int *tab, int s, int e){
- for (int i = 0; i < arraySize; i++) {
- tab[i] = (rand()%(e-s)+s);
- }
- }
- double timer() {
- return ((double)(stop - start) / CLOCKS_PER_SEC);
- }
- void printArray(int tab[]) {
- if(print){
- for (int i = 0; i < arraySize; i++) {
- cout << tab[i] << " ";
- }
- cout << endl;
- }
- }
- void printArrayAbs(int tab[]) {
- for (int i = 0; i < arraySize; i++) {
- cout << tab[i] << " ";
- }
- cout << endl;
- }
- void insertionSort(int arr[]) {
- int tab[arraySize];
- memcpy(tab, arr, sizeof(tab));
- compares = 0;
- switches = 0;
- start = clock();
- int i, key, j;
- for (i = arraySize-2; i >= 0; i--) {
- key = tab[i];
- j = i + 1;
- compares++;
- while (j < arraySize && tab[j] > key) {
- compares++;
- switches++;
- tab[j - 1] = tab[j];
- j = j + 1;
- }
- tab[j - 1] = key;
- }
- stop = clock();
- if(keyb==1){
- printArrayAbs(tab);
- }
- }
- int partitionn(int arr[], int low, int high){
- int pivot = arr[high];
- int i = (low - 1);
- for (int j = low; j <= high - 1; j++)
- {
- if (arr[j] > pivot)
- {
- compares++;
- i++;
- swapp(&arr[i], &arr[j]);
- }
- }
- swapp(&arr[i + 1], &arr[high]);
- return (i + 1);
- }
- void quickSort(int arr[], int low, int high){
- if (low < high)
- {
- int pi = partitionn(arr, low, high);
- if(keyb)
- cout<<arr[pi]<<" ";
- quickSort(arr, low, pi - 1);
- quickSort(arr, pi + 1, high);
- }
- }
- void setQuickSort(int arr[]) {
- int tab[arraySize];
- memcpy(tab, arr, sizeof(tab));
- compares = 0;
- switches = 0;
- if(keyb)
- cout<<"Pivot: ";
- start = clock();
- quickSort(tab, 0, arraySize-1);
- printf("\n");
- stop = clock();
- if(keyb==1)
- printArrayAbs(tab);
- }
- void mergee(int arr[], int l, int m, int r){
- //switches++;
- int i, j, k;
- int n1 = m - l + 1;
- int n2 = r - m;
- int L[n1], R[n2];
- for (i = 0; i < n1; i++)
- L[i] = arr[l + i];
- for (j = 0; j < n2; j++)
- R[j] = arr[m + 1 + j];
- i = 0;
- j = 0;
- k = l;
- while (i < n1 && j < n2)
- {
- compares++;
- if (L[i] >= R[j])
- {
- arr[k] = L[i];
- i++;
- }
- else
- {
- arr[k] = R[j];
- j++;
- }
- k++;
- }
- while (i < n1)
- {
- arr[k] = L[i];
- i++;
- k++;
- }
- while (j < n2)
- {
- arr[k] = R[j];
- j++;
- k++;
- }
- }
- void mergeSort(int arr[], int l, int r){
- if (l < r)
- {
- int m = l + (r - l) / 2;
- mergeSort(arr, l, m);
- mergeSort(arr, m + 1, r);
- mergee(arr, l, m, r);
- }
- }
- void setMergeSort(int arr[]){
- int tab[arraySize];
- memcpy(tab, arr, sizeof(tab));
- compares = 0;
- switches = 0;
- start = clock();
- mergeSort(tab, 0, arraySize-1);
- stop = clock();
- if(keyb)
- printArrayAbs(tab);
- }
- void heapify(int arr[], int n, int i){
- int smallest = i;
- int l = 2 * i + 1;
- int r = 2 * i + 2;
- if (l < n && arr[l] < arr[smallest]){
- compares++;
- smallest = l;
- }
- if (r < n && arr[r] < arr[smallest]){
- compares++;
- smallest = r;
- }
- if (smallest != i) {
- compares++;
- swapp(&arr[i], &arr[smallest]);
- heapify(arr, n, smallest);
- }
- }
- void heapSort(int arr[]){
- int tab[arraySize];
- memcpy(tab, arr, sizeof(tab));
- compares = 0;
- switches = 0;
- start = clock();
- for (int i = arraySize / 2 - 1; i >= 0; i--)
- heapify(arr, arraySize, i);
- for (int i = arraySize - 1; i >= 0; i--) {
- swapp(&arr[0], &arr[i]);
- heapify(arr, i, 0);
- }
- stop = clock();
- if(keyb==1)
- printArrayAbs(arr);
- }
- void shellSort(int arr[]){
- int tab[arraySize];
- memcpy(tab, arr, sizeof(tab));
- compares = 0;
- switches = 0;
- printArray(tab);
- if(keyb)
- cout<<"Gap: ";
- start = clock();
- for (int gap = arraySize / 2; gap > 0; gap /= 2){
- for (int i = gap; i < arraySize; i += 1){
- int temp = tab[i];
- int j;
- compares++;
- for (j = i; j >= gap && tab[j - gap] > temp; j -= gap){
- switches++;
- compares++;
- tab[j] = tab[j - gap];
- }
- tab[j] = temp;
- }
- if(keyb)
- cout<<gap<<" ";
- }
- stop=clock();
- if(keyb)
- cout<<endl;
- if(keyb==1){
- printArrayAbs(tab);
- }
- }
- void formArray(int tab[], int s, int e, int type){
- if(type==0){
- generateArray(tab, s, e);
- }
- if(type==1){
- for(int i=0; i<arraySize; i++){
- tab[i]=i;
- }
- }
- if(type==2){
- for(int i=0; i<arraySize; i++){
- tab[i]=arraySize-i-1;
- }
- }
- if(type==3){
- if(arraySize%2){
- for(int i=0; i<=arraySize/2; i++){
- tab[arraySize/2-i]=2*i;
- tab[arraySize/2+i+1]=2*i+1;
- }
- }else{
- for(int i=0; i<=arraySize/2-1; i++){
- tab[arraySize/2-1-i]=2*i;
- tab[arraySize/2+i]=2*i+1;
- }
- }
- }
- if(type==4){
- if(arraySize%2){
- for(int i=0; i<=arraySize/2; i++){
- tab[arraySize/2-i-1]=arraySize-2*i-2;
- tab[arraySize/2+i]=arraySize-2*i-1;
- }
- }else{
- for(int i=0; i<=arraySize/2-1; i++){
- tab[arraySize/2-1-i]=arraySize - 2*i-2;
- tab[arraySize/2+i]=arraySize - 2*i-1;
- }
- }
- }
- }
- void menu(int &choice, int &sortC){
- cout<<"1. Generuj liczby"<<endl;
- cout<<"2. Wczytaj liczby z pliku"<<endl;
- cout<<"3. Wczytaj liczby z klawiatury"<<endl;
- choice=(getch()-48)*10;
- system("cls");
- if(choice==10){
- cout<<"Typ generowanej tablicy"<<endl;
- cout<<"1. Randomowa"<<endl;
- cout<<"2. Rosnaca"<<endl;
- cout<<"3. Malejaca"<<endl;
- cout<<"4. V-ksztaltna"<<endl;
- cout<<"5. A-ksztaltna"<<endl;
- choice+=(getch()-49);
- system("cls");
- }
- cout<<"Wielkosc tablicy: ";
- cin>>arraySize;
- system("cls");
- cout<<"Sortowanie"<<endl;
- cout<<"1. Insertion Sort"<<endl;
- cout<<"2. Shell Sort"<<endl;
- cout<<"3. Heap Sort"<<endl;
- cout<<"4. Merge Sort"<<endl;
- cout<<"5. Quick Sort"<<endl;
- sortC=getch()-48;
- system("cls");
- }
- void head(){
- int choice=1;
- int sortC=1;
- menu(choice, sortC);
- //cout<<arraySize<<endl;
- //cout<<choice;
- int tab[arraySize];
- keyb=(choice/10==3);
- if(choice/10==1){
- formArray(tab, genMin, genMax, choice%10);
- printArray(tab);
- }
- if(choice/10==2){
- file.open("data.txt");
- loadFile(tab);
- printArray(tab);
- }
- if(choice/10==3){
- keyboard(tab);
- }
- if(!error){
- switch(sortC)
- {
- case 1:
- printf("Insertion Sort:\n");
- insertionSort(tab);
- break;
- case 2:
- printf("Shell Sort:\n");
- shellSort(tab);
- break;
- case 3:
- printf("Heap Sort:\n");
- heapSort(tab);
- break;
- case 4:
- printf("Merge Sort:\n");
- setMergeSort(tab);
- break;
- case 5:
- printf("Quick Sort:\n");
- setQuickSort(tab);
- break;
- }
- printf("Time:\t %.3f \n", timer());
- printf("Compares: %.i \n", compares);
- printf("Switches: %.i \n", switches);
- printf("\n");
- }
- getch();
- }
- int main()
- {
- srand(time(NULL)); //seed
- head();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement