Quicksort для строкового массива

Question

Просмотрев статьи, учебные пособия и решения во всем мире, я не нашел ничего, что объясняет, как использовать quicksort для строковых массивов. Все примеры, которые я нашел, имеют либо «int», либо «char».

Это мой отредактированный код.

#include <iostream> 
#include <fstream> 
#include <cstdlib> 
#include <time.h> 
#include <string> 
#include <ctime> 
#include <stdio.h> 



using namespace std; 

int count; 
template <class T> 
void printArray(T ar[], int sz); 
template <class T> 
void bubbleSort(T ar[], int sz); 
void quickSortMain(string items[], int ct); 
void quickSort(string items[], int left, int right); 

////////////////////////////////////////////////////////////////////////// 
// Main Function Implementation 
////////////////////////////////////////////////////////////////////////// 

int main() { 
    int numOfData = 50000; 
    string line, temp; 
    ofstream resultFile; 
    ofstream tableFile; 
    double data[100][2]; 
    string patient[numOfData]; 
    ifstream dataFile("shufflePatient.txt"); 
    int i; 
    int SIZE = 0; 

    cout << "Program to shuffle data" << endl << endl; 
    cout << "This program will calculate swapping processes and running time."; 


    /*Storing data*/ 
    cout << "Reading data in process.." << endl; 
    if (dataFile.is_open()) { 
     i=-1; 
     while (dataFile.good()) { 
      getline (dataFile, line); 
      if (i>=0) patient[i] = line; 
      i++; 
     } 
     dataFile.close(); 
    } 

    SIZE = 5; 
    quickSortMain(patient, 5); 


    /*Writing to file*/ 
    cout << "Writing to file.." << endl; 
    resultFile.open ("test.txt"); 
    for (int i=0 ; i<numOfData ; i++) { 
     resultFile << patient[i] << "\n"; 
    } 
    resultFile.close(); 
    system("pause"); 
    return 0; 
} 


void quickSortMain(string items[], int ct) 
{ 
    quickSort(items, 0, ct-1); 
} 


void quickSort(string items[], int left, int right) 
{ 
    int i, j; 
    char *x; 
    string temp[10]; 

    i = left; 
    j = right; 
    x = items[(left+right)/2]; 

    do { 
    while((strcmp(items[i],x) < 0) && (i < right)) { 
     i++; 
    } 
    while((strcmp(items[j],x) > 0) && (j > left)) { 
     j--; 
    } 
    if(i <= j) { 
     strcpy(temp, items[i]); 
     strcpy(items[i], items[j]); 
     strcpy(items[j], temp); 
     i++; 
     j--; 
    } 
    } while(i <= j); 

    if(left < j) { 
    quickSort(items, left, j); 
    } 
    if(i < right) { 
    quickSort(items, i, right); 
    } 
} 









//---------------------------------------------------------------------------- 
// prints array of size size 
//---------------------------------------------------------------------------- 
template <class T> 
void printArray(T patient[], int size) 
{ 
    for(int i = 0; i < size; i++) 
    cout << patient[i] << " "; 
    cout << endl; 
} 




//---------------------------------------------------------------------------- 
// sorts array of size size by Bubble Sort method 
//---------------------------------------------------------------------------- 
template <class T> 
void bubbleSort(T patient[], int size) //returning an int 
{ 
    bool noChange = true; 
    for(int i = size; i > 0; i--) 
    { 
    noChange = true; 
    for(int j = 1; j < i; j++) 
    { 
     if(patient[j] < patient[j - 1]) 
     { 
     swap(patient[j], patient[j-1]); 
     count = count + 1; 
     noChange = false; 
     } 
    } 
    if (noChange) 
     return ; 
    } 
} 

ошибка я получил, был в этой линии:

x = items[(left+right)/2]; 

Я изменил

char x*; в string x;

Я не знаю, если это было правильно. Теперь ошибка im get заключается в том, что strcmp и strcpy не объявлены. Любая помощь в том, что я должен делать дальше?

Answer 1

string patient[numOfData]; 

против

template <class T> 
void quickSortMain(char items[][10], int ct) 

против

quickSortMain(patient, 5); 

quickSortMain ожидает, что массив char[10], а не string[]. Не только это, но и зависит от параметра шаблона. Снимите template <class T> и замените char[][10] на string[].