quicksort를 사용하여 문자열 정렬

Question

문자열 배열을 정렬하는 데 quicksort를 구현하는 데 문제가 있습니다. 나는 또한 비교적 새로운 C++이기 때문에 여전히 거기에있는 몇 가지 문제로 고심하고있다. 지금은 내 코드가 올바르게 읽고 문자열 배열을 생성하지만 내 퀵 정렬 알고리즘을 사용하려고 할 때 문제가 발생합니다. 제가 처음으로 겪고있는 첫 번째 문제는 재귀가해야 할 때 멈추지 않는다고 생각한다는 것입니다. 나는 quicksort가 약간 실행 된 후에 세분화 오류가 발생합니다.

코드 (수정이) :

#include "MyParser.h" 
    #include <iostream> 
    #include <fstream> 
    #include <string> 

    void resize(string*& words, int size) 
    { 
    string* newArray = new string[size*2]; 

    for (int i = 0; (i < size)&&(i<size*2); i++) 
     newArray[i] = words[i]; 

    for (int i = size; i < size*2; i++) 
    newArray[i] = ""; 

    delete[] words; 
    words = newArray; 
    } 

    void partitionArray(string*& words, int& left, int& right, int pi) 
    { 
    int i = left; 
    int j = right; 
    string tmp; 
    string pivot = words[pi]; 
    while (i < j) { 
     string str1 = words[i]; 
     string str2 = words[j]; 
     while ((str1.compare(pivot) < 0) && (i < right)) 
      i++; 
     while ((str2.compare(pivot) >= 0) && (j > left)) 
      j--; 
     if (i <= j) 
     { 
      tmp = words[i]; 
      words[i] = words[j]; 
      words[j] = tmp; 
      i++; 
       j--; 
      } 
     }; 
    } 

    void quickSort(string*& words, int left, int right) 
    { 
     int i = left; 
     int j = right; 
     string tmp; 
     string pivot = words[(left + right)/2]; 
     /* partition */ 
     int pivotIndex = (left + right)/2; 
     pivotIndex = partitionArray(words, 0, right, pivotIndex); 
     cout << "start recursion" << endl; 
     /* recursion */ 
     if (left < j) 
      quickSort(words, left, j); 
     if (i < right) 
      quickSort(words, i, right); 
    } 

    int main() 
    { 
     // define file reader 
     ofstream outData; 
     outData.open("logData.txt"); 

     Parser* myParser = new Parser("testData.txt"); 
     int sizeOfArray = 500; 
     string* words = new string[sizeOfArray]; 
     int index = 0; 
     while(myParser->hasTokens()) 
     { 
      if (index >= sizeOfArray) 
      { 
       resize(words, sizeOfArray); 
       sizeOfArray = sizeOfArray*2; 
      } 
      string currentWord = myParser->nextToken(); 
      if (currentWord != "") 
      { 
       words[index] = currentWord; 
       index++; 
      } 
     } 
     int lastWordInArrayIndex = index; 
     quickSort(words, 0, lastWordInArrayIndex); 
     return 0; 
    } 

이에 어떤 도움을 크게 감상 할 수있다!

는 올바르게 다음 11 개 요소를 정렬합니다 지금

수정 : adfgh를 btyui eerty fqwre kyuio verty zsdfg

zbsdf yrtyu wwert하지만 때를 시도 dfghj 다음과 같은 구문 분석 된 텍스트를 정렬하십시오. 단락 기호는 모두 사용하지 마십시오. 단 하나의 하이픈 또는 아포스트로가있는 단어가있는 "like-this"가 더 나쁩니다. 같은 프 "그들이있어"가 종료되지 않습니다

사흘 싸움 후, 프린스 스테판 Arkadyevitch Oblonsky - 그가 패션을 전 세계에 에 불렸다 스티 바는, 자신의 평소 시간에 일어 났는데, 즉, 오전 8시에 아침에, 그의 아내의 침실에있는 것이 아니라 그의 가죽 소파에 소파가 있습니다. 그는 그의 뚱뚱한, well-cared를 뒤집었다. 마치 그가 긴 소파에 잠길 것 인 것처럼, 자는 잠자는 소파에 다시 잠을 자다. 그는 활발하게 다른 쪽 에 베개를 안기고 그것에 그의 얼굴을 묻었다; 하지만 모두 한 번에 그는 뛰어 올라 소파에 에 앉아 눈을 떴습니다.

"예, 어떻게 되었습니까?" 그는 자신의 꿈을 생각했다. "잘 지냈어! 알라빈이 저녁 식사를하고 있었어 다름슈타트가 아니라 다름슈타트가 아니라 미국인 이었어 그래,하지만 다름슈타트는 미국에 있었어 네, 알라빈이 저녁을 내고 있었다 유리 테이블과 테이블은 노래했다. Il mio tesoro - Il mio tesoro 그러나 더 좋은 무엇인가. 그리고 테이블의 약간의 경사 자 들인 의 약간의 경사가 있었다. 그리고 그들은 또한 여성이었다. "그는 가 기억하고 있었다.

다시이 문제에 대한 도움을 주시면 매우 감사하겠습니다.

Answer 1

귀하의 quickSort 작동합니다 실제로 같이 Recurse 무기한 : left < right 경우 함수가 또 다시 같은 매개 변수를 사용하여 재귀 적으로 호출 할 수 있도록

void quickSort(string*& words, int left, int right) 
{ 
    int i = left; 
    int j = right; 

    ... 

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

i, j, left 및 right가, 그 함수의 아무 곳이나 수정되지 않습니다 .