Проблемы с программой для тестирования Shell, Insertion и Quick Sort

Итак, эта программа должна тестировать запуск вставки, оболочки и быстрой сортировки с 3 различными текстовыми файлами целых чисел, но по какой-то причине, за пределами моего понимания, ни один из результатов, кроме количества элементов, не отображается. Предполагается показать количество секунд и тактовых циклов, которые требуются для запуска каждой сортировки с помощью clock (). Пожалуйста, кто-нибудь может сказать мне, почему это не работает? Я в тупике!

#include "targetver.h"#include <time.h>
#include <stdio.h>
#include <dos.h>
#include <iomanip>
#include <fstream>
#include <string>
#include <stdio.h>
#include <tchar.h>
#include <queue>
#include <stack>
#include <vector>
#include<iostream>
#include<cstdio>
#include<sstream>
#include<algorithm>
using namespace std;// insertion sort function
void insertionSort(vector<int> arr, int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;

/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

// shell sort function
void shellSort(vector<int> arr, int n)
{
// Start with a big gap, then reduce the gap
for (int gap = n / 2; gap > 0; gap /= 2)
{
// Do a gapped insertion sort for this gap size.
// The first gap elements a[0..gap-1] are already in gapped order
// keep adding one more element until the entire array is
// gap sorted
for (int i = gap; i < n; i += 1)
{
// add a[i] to the elements that have been gap sorted
// save a[i] in temp and make a hole at position i
int temp = arr[i];

// shift earlier gap-sorted elements up until the correct
// location for a[i] is found
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];

//  put temp (the original a[i]) in its correct location
arr[j] = temp;
}
}
}

// function that swaps two elements
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}

/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition(vector<int> arr, int low, int high)
{
int pivot = arr[high];    // pivot
int i = (low - 1);  // Index of smaller element

for (int j = low; j <= high - 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++;    // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

/* The main function that implements QuickSort
arr --> Array to be sorted,
low  --> Starting index,
high  --> Ending index */
void quickSort(vector<int> arr, int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);

// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

// print array function
void printArray(vector<int> arr)
{
int z = arr.size();
int i;
for (i = 0; i < z; i++)
printf("%d ", arr[i]);
printf("n");
}int main()
{
int max = 10000000;
vector<int> arr;
arr.reserve(max);
double start, end, elapsed_clock, elapsed_time;
int low, high, n;string name;//holds first file name entered by user
ifstream fin;

cout << "Please enter the file name you wish to read from: ";//asks user for file name
getline(cin, name);//gets file name
fin.open(name);//opens file with set file name
if (fin.fail())//run if file name is incorrect or fails to load
{
cout << "Error opening " << name << "\n";//print error and file name
}
else
{
cout << "\nFile opened successfully, please wait." << endl;

// holds data read from file
int theData;

do // loop reads file till end
{
fin >> theData;

if (fin.good())
{
arr.push_back(theData);
}
//if read failed, check to see if file end was cause, otherwise print message and close
else if (!fin.eof())
{
cout << "\nThe file could not be read" << endl;
}
//runs while data being read
} while (!fin.eof());

}
fin.close();

n = sizeof(arr) / sizeof(arr[0]);
start = clock();
insertionSort(arr, n);
end = clock();
elapsed_clock = end - start;
elapsed_time = ((end - start) / CLK_TCK);
cout << "Insertion Sort\t: " << arr.size() << " items" << "     " << elapsed_clock << " ticks" << "     " << elapsed_time << " sec\n";
start = clock();
shellSort(arr, n);
end = clock();
elapsed_clock = end - start;
elapsed_time = ((end - start) / CLK_TCK);
cout << "Shell Sort\t: " << arr.size() << " items" << "     " << elapsed_clock << " ticks" << "     " << elapsed_time << " sec\n";
start = clock();
quickSort(arr, 0, n - 1);
end = clock();
elapsed_clock = end - start;
elapsed_time = ((end - start) / CLK_TCK);
cout << "Quick Sort\t: " << arr.size() << " items" << "     " << elapsed_clock << " ticks" << "     " << elapsed_time << " sec\n";
printArray(arr);
cout << endl;//spacecout << "Please enter the file name you wish to read from: ";//asks user for file name
getline(cin, name);//gets file name
fin.open(name);//opens file with set file name
if (fin.fail())//run if file name is incorrect or fails to load
{
cout << "Error opening " << name << "\n";//print error and file name
}
else
{
cout << "\nFile opened successfully, please wait." << endl;

// holds data read from file
int theData;

do // loop reads file till end
{
fin >> theData;

if (fin.good())
{
arr.push_back(theData);
}
//if read failed, check to see if file end was cause, otherwise print message and close
else if (!fin.eof())
{
cout << "\nThe file could not be read" << endl;
}
//runs while data being read
} while (!fin.eof());

}
fin.close();

n = sizeof(arr) / sizeof(arr[0]);
start = clock();
insertionSort(arr, n);
end = clock();
elapsed_clock = end - start;
elapsed_time = ((end - start) / CLK_TCK);
cout << "Insertion Sort\t: " << arr.size() << " items" << "     " << elapsed_clock << " ticks" << "     " << elapsed_time << " sec\n";
start = clock();
shellSort(arr, n);
end = clock();
elapsed_clock = end - start;
elapsed_time = ((end - start) / CLK_TCK);
cout << "Shell Sort\t: " << arr.size() << " items" << "     " << elapsed_clock << " ticks" << "     " << elapsed_time << " sec\n";
start = clock();
quickSort(arr, 0, n - 1);
end = clock();
elapsed_clock = end - start;
elapsed_time = ((end - start) / CLK_TCK);
cout << "Quick Sort\t: " << arr.size() << " items" << "     " << elapsed_clock << " ticks" << "     " << elapsed_time << " sec\n";
printArray(arr);
cout << endl;//spacecout << "Please enter the file name you wish to read from: ";//asks user for file name
getline(cin, name);//gets file name
fin.open(name);//opens file with set file name
if (fin.fail())//run if file name is incorrect or fails to load
{
cout << "Error opening " << name << "\n";//print error and file name
}
else
{
cout << "\nFile opened successfully, please wait." << endl;

// holds data read from file
int theData;

do // loop reads file till end
{
fin >> theData;

if (fin.good())
{
arr.push_back(theData);
}
//if read failed, check to see if file end was cause, otherwise print message and close
else if (!fin.eof())
{
cout << "\nThe file could not be read" << endl;
}
//runs while data being read
} while (!fin.eof());

}
fin.close();

n = sizeof(arr) / sizeof(arr[0]);
start = clock();
insertionSort(arr, n);
end = clock();
elapsed_clock = end - start;
elapsed_time = ((end - start) / CLK_TCK);
cout << "Insertion Sort\t: " << arr.size() << " items" << "     " << elapsed_clock << " ticks" << "     " << elapsed_time << " sec\n";
start = clock();
shellSort(arr, n);
end = clock();
elapsed_clock = end - start;
elapsed_time = ((end - start) / CLK_TCK);
cout << "Shell Sort\t: " << arr.size() << " items" << "     " << elapsed_clock << " ticks" << "     " << elapsed_time << " sec\n";
start = clock();
quickSort(arr, 0, n - 1);
end = clock();
elapsed_clock = end - start;
elapsed_time = ((end - start) / CLK_TCK);
cout << "Quick Sort\t: " << arr.size() << " items" << "     " << elapsed_clock << " ticks" << "     " << elapsed_time << " sec\n";
printArray(arr);
cout << endl;//space

system("Pause");//waits for user input
return 0;
}

0

Решение

Вы должны передать все векторы в функцию по ссылке, а не по значению.

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]