Quicksort 알고리즘이 제대로 작동하지 않습니다.

Question

#include <iostream> 

#include <string> 

using namespace std; 

//Iterates over the string array appNames displaying each application 
//name in a separate line. There are appCount elements in the array 

void displayAllApplicationNames(string appNames[], int appCount); 

//Swaps strings in string array appNames between appIndex1 and appIndex2 

void swapAppNames(int appIndex1, int appIndex2, string appNames[]); 

//Splits string array appNames around a pivot index p (the pivot). 
//Elements below index p are less than elements above index p. 
//The function returns the pivot p 

int pivot(int first, int last, string appNames[]); 

//Implements the QuickSort algorithm to sort string array 
//appNames between indeces first and last 


void quickSort(int first, int last, string appNames[]); 


void main() 

{ 

    string appNames[] = 

    { 

     "4) Pages", "2) Keynote", "3) Numbers", 

     "8) Word", "5) PowerPoint", "1) Excel", 

     "0) Documents", "6) Presentation", "7) Sheets" 

    }; 


    displayAllApplicationNames(appNames, 9); 

    swapAppNames(3, 6, appNames); 

    displayAllApplicationNames(appNames, 9); 

    quickSort(0, 8, appNames); 

    displayAllApplicationNames(appNames, 9); 


    getchar(); 


} 


void displayAllApplicationNames(string appNames[], int appCount) 

{ 

     for(appCount = 0; appCount <= 8; appCount++) 
     { 

     cout << "[" << appCount << "]\t"<< appNames[appCount] << endl; 

     } 

     if(appCount < 0 || appCount > 8) 
     { 

      cout << "_________" <<endl; 
     } 


} 


void swapAppNames(int appIndex1, int appIndex2, string appNames[]) 

{ 
    string temp = appNames[appIndex1]; 
    appNames[appIndex1] = appNames[appIndex2]; 
    appNames[appIndex2] = temp; 

} 


int pivot(int first, int last, string appNames[]) 

{ 
    int pivotIndex, mid = (first + last)/2; 
    swapAppNames(first, mid, appNames); 
    pivotIndex = first; 
    string pivotValue = appNames[first]; 
    for (int i = first + 1; i <= last; i++) 
    { 
     if (appNames[i] < pivotValue) 
     { 
      pivotIndex++; 
      swapAppNames(pivotIndex, i, appNames); 
     } 

     swapAppNames(first, last, appNames); 

     return pivotIndex; 
    } 


} 

void quickSort(int first, int last, string appNames[]) 

{ 
    if (first < last) 
    { 
     int p = pivot(first, last, appNames); 
     quickSort(first, p - 1, appNames); 
     quickSort(p + 1, last, appNames); 

    } 

} 

목표는 문자열 배열 "appNames"에서 이름을 정렬하는 것입니다. 이름에 숫자를 추가하여 순서가 틀림 없음을 보여 주지만 프로그램을 실행하면 올바르게 정렬되지 않는 것 같습니다. 아무도 내가 잘못 가고 있다고 말할 수 있습니까?

저는 며칠 동안 이것을 보지 않고 있습니다.

편집 : 해결책은 다음과 같습니다. 답장을 한 모든 사람들에게 큰 감사를드립니다. 몇 가지 변수의 위치를 ​​교환하고 퀵 소트 알고리즘을 읽어야했습니다. 당신이 그것을 게시 된

int pivot(int first, int last, string appNames[]) 

{ 
    int pivotIndex, mid = (first + last)/2; 
    swapAppNames(first, mid, appNames); 
    pivotIndex = first; 
    string pivotValue = appNames[first]; 
    for (int i = first + 1; i <= last; i++) 
    { 
     if (appNames[i] < pivotValue) 
     { 
      pivotIndex++; 
      swapAppNames(pivotIndex, i, appNames); 
     } 


    } 

    swapAppNames(pivotIndex, first, appNames); 

     return pivotIndex; 

}

Answer 1

코드는 여전히 올바르지 않습니다. 다음은 작동하는 버전입니다. 나는 몇 가지 변화를했다.

피벗 기능에서 mid 휴리스틱을 제거했습니다. 귀하의 과제가 최악의 시나리오를 고려하도록 명시 적으로 요구하지 않는 한 그것은 소음입니다. 그리고 그랬다면 더 나은 경험적 방법이 필요합니다. 또한 스와핑이 덜 효과적이지만 더 직관적 인 버전으로 바뀌는 방식을 변경했습니다.

quickSort 및 pivot 인터페이스에서 사용 된 다른 변경 사항은 last이었습니다. last이 "끝을 지나친 것"을 의미하면 더 좋습니다. 실제로 last이 마지막 항목이면 빈 목록을 나타낼 방법이 없습니다. 귀하의 표기법 (0,0)은 길이가 1이고, (0,1)은 길이가 2 등이며, 길이는 (마지막 - 처음) +1로 계산됩니다. last이 "끝을 지나서 한"이면, 비어 있습니다 목록은 (0,0), (0,1)은 길이가 1 등이며 길이는 단순히 (마지막 - 처음)입니다. C++을 계속 사용한다면 이것이 STL이 작동하는 방식이라는 것을 알 수 있으므로 지금 배우는 것이 유용합니다.

#include <iostream> 
#include <string> 

using namespace std; 

//Iterates over the string array appNames displaying each application 
//name in a separate line. There are appCount elements in the array 
void displayAllApplicationNames(string appNames[], int appCount); 


//Swaps strings in string array appNames between appIndex1 and appIndex2 
void swapAppNames(int appIndex1, int appIndex2, string appNames[]); 


//Splits string array appNames around a pivot index p (the pivot). 
//Elements below index p are less than elements above index p. 
//The function returns the pivot p 
int pivot(int first, int last, string appNames[]); 


//Implements the QuickSort algorithm to sort string array 
//appNames between indices first and last 
void quickSort(int first, int last, string appNames[]); 


int main() { 
    string appNames[] = { 
    "4) Pages", "2) Keynote", "3) Numbers", 
    "8) Word", "5) PowerPoint", "1) Excel", 
    "0) Documents", "6) Presentation", "7) Sheets" }; 
    displayAllApplicationNames(appNames, 9); 
    swapAppNames(3, 6, appNames); 
    displayAllApplicationNames(appNames, 9); 
    quickSort(0, 9, appNames); 
    displayAllApplicationNames(appNames, 9); 
    return 0; } 


void displayAllApplicationNames(string appNames[], int appCount) { 
    for (int i = 0; i < appCount; ++i) { 
    cout << "[" << i << "]\t" << appNames[i] << endl; } 

    cout << "_________" << endl; } 


void swapAppNames(int appIndex1, int appIndex2, string appNames[]) { 
    string temp = appNames[appIndex1]; 
    appNames[appIndex1] = appNames[appIndex2]; 
    appNames[appIndex2] = temp; } 


int pivot(int p, int n, string a[]) { 
    for (int i = p + 1; i < n; ++i) { 
    if (a[i] < a[p]) { 
     swapAppNames(i, p + 1, a); 
     swapAppNames(p, p + 1, a); 
     ++p; } } 

    return p; } 


void quickSort(int first, int last, string a[]) { 
    if (first < last) { 
    int p = pivot(first, last, a); 
    quickSort(first, p, a); 
    quickSort(p + 1, last, a); } }