쉘, 삽입 및 빠른 정렬을 테스트하는 프로그램의 문제

Question

따라서이 프로그램은 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;//space 




    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;//space 



    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;//space 

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

Answer 1

모든 벡터를 값으로 전달하지 않고 참조로 전달해야합니다.