Quicksorting alphabetisch und nach Zeichenlänge

Question

Ich schreibe gerade ein Programm, das eine ziemlich große Textdatei liest und die Textdatei alphabetisch und nach Zeichenlänge sortiert. Ich habe dafür einen Quicksort implementiert. Das Problem, das ich habe und hoffentlich Klarheit bekommen wird, ist, dass ich zwei Methoden für Quiksorting habe. Eines, das quickSortLen hier ist der Code

void SortingCompetition::quickSortLen(vector<char*>& words, int left, int right){ 
    int i, j, middle, underMiddle, overMiddle; 
    char* pivot; 

    //Median of FIVE pivot point 
    i = left; 
    j = right; 
    middle = left + (right - left)/2; 
    underMiddle = left + (middle - left)/2; 
    overMiddle = middle + (right - middle)/2; 

    //Right and Left 
    if(strlen(words[right]) < strlen(words[left])) 
    { 
     swap(words[right], words[left]); 

    } 

    // 4/5 and left 
    if(strlen(words[overMiddle]) < strlen(words[left])) 
    { 
     swap(words[overMiddle], words[left]); 

    } 

    //Middle and Left 
    if(strlen(words[middle]) < strlen(words[left])) 
    { 
     swap(words[middle], words[left]); 

    } 

    // 2/5 and Middle 
    if(strlen(words[underMiddle]) < strlen(words[left])) 
    { 
     swap(words[underMiddle], words[left]); 

    } 

    //right and 4/5 
    if(strlen(words[right]) < strlen(words[underMiddle])) 
    { 
     swap(words[right], words[underMiddle]); 

    } 

    //Right and Middle 
    if(strlen(words[overMiddle]) < strlen(words[underMiddle])) 
    { 
     swap(words[overMiddle], words[underMiddle]); 

    } 

    //Middle and UnderMiddle 
    if(strlen(words[middle]) < strlen(words[underMiddle])) 
    { 
     swap(words[middle], words[underMiddle]); 

    } 

    //Right and Middle 
    if(strlen(words[right]) < strlen(words[middle])) 
    { 
     swap(words[right], words[middle]); 

    } 

    //OverMiddle and Middle 
    if(strlen(words[overMiddle]) < strlen(words[middle])) 
    { 
     swap(words[overMiddle], words[middle]); 

    } 

    //Right and OverMiddle 
    if(strlen(words[right]) < strlen(words[overMiddle])) 
    { 
     swap(words[right], words[overMiddle]); 

    } 

    //PIVOT POINT ESTABLISHED 
    pivot = words[middle]; 

    //Partition 
    while (i <= j) 
    { 
     //Check from start 
     while (strlen(words[i]) < strlen(pivot)) 
     { 
       ++i; 
     } 

     //Check from end 
     while (strlen(words[j]) > strlen(pivot)) 
     { 
       --j; 
     } 

     //Switch 
     if(i <= j) 
     { 
      swap(words[i], words[j]); 
      ++i; 
      --j; 
     } 

    } 


    //Recursion 
    if (left < j) 
    { 
     quickSortLen(words, left, j); 
    } 

    if(i < right) 
    { 
     quickSortLen(words, i, right); 
    } 

} 

und als i quickSortAlph haben hier ist der Code für das

void SortingCompetition::quickSortAlph(vector<char*>& words, int left, int right){ 
int i, j, middle, underMiddle, overMiddle; 
char* pivot; 
int x = 1; 
//Median of FIVE pivot point 
i = left; 
j = right; 
middle = left + (right - left)/2; 
underMiddle = left + (middle - left)/2; 
overMiddle = middle + (right - middle)/2; 

//Right and Left 
if(strcmp(words[right], words[left]) < 0) 
{ 
    swap(words[right], words[left]); 

} 

// 4/5 and left 
if(strcmp(words[overMiddle], words[left]) < 0) 
{ 
    swap(words[overMiddle], words[left]); 

} 

//Middle and Left 
if(strcmp(words[middle], words[left]) < 0) 
{ 
    swap(words[middle], words[left]); 

} 

// 2/5 and Middle 
if(strcmp(words[underMiddle], words[left]) < 0) 
{ 
    swap(words[underMiddle], words[left]); 

} 

//right and 4/5 
if(strcmp(words[right], words[underMiddle]) < 0) 
{ 
    swap(words[right], words[underMiddle]); 

} 

//Right and Middle 
if(strcmp(words[overMiddle], words[underMiddle]) < 0) 
{ 
    swap(words[overMiddle], words[underMiddle]); 

} 

//Middle and UnderMiddle 
if(strcmp(words[middle], words[underMiddle]) < 0) 
{ 
    swap(words[middle], words[underMiddle]); 

} 

//Right and Middle 
if(strcmp(words[right], words[middle]) < 0) 
{ 
    swap(words[right], words[middle]); 

} 

//OverMiddle and Middle 
if(strcmp(words[overMiddle], words[middle]) < 0) 
{ 
    swap(words[overMiddle], words[middle]); 

} 

//Right and OverMiddle 
if(strcmp(words[right], words[overMiddle]) < 0) 
{ 
    swap(words[right], words[overMiddle]); 

} 

//PIVOT POINT ESTABLISHED 
pivot = words[middle]; 

//Partition 
while (i <= j) 
{ 
     //if((strcmp(words[i], pivot) < 0) && (strcmp(words[j], pivot) < 0) 
     //Check from start 
     while (strcmp(words[i], pivot) < 0) 
     { 
      ++i; 
     } 

     //Check from end 
     while (strcmp(words[j], pivot) > 0) 
     { 
      --j; 
     } 

     //Switch 
     if((i <= j)) 
     { 
      swap(words[i], words[j]); 
      ++i; 
      --j; 
     }else{ 
      i++; 
      j--; 
     } 

} 


//Recursion 
if (left < j) 
{ 
    quickSortAlph(words, left, j); 
} 

if(i < right) 
{ 
    quickSortAlph(words, i, right); 
} 
} 

beide arbeiten, wie sie sollten aber im Probleme, die Kombination der beiden, weil ein Wort wie August wird weniger Ascii Wert als Bravo haben, aber die Länge ist von Bravo ist weniger als August. irgendwelche Vorschläge, wie man die zwei kombiniert?

Answer 1

Müssen Sie wirklich Ihre eigene schnelle Sortierung schreiben? Wenn Sie das nicht tun, können Sie std::sort mit einem benutzerdefinierten Vergleich functor verwenden.

struct string_cmp 
{ 
    bool operator()(const std::string& lhs, const std::string& rhs) 
    { 
     if (lhs.size() == rhs.size()) 
      return lhs < rhs; 
     else 
      return lhs.size() < rhs.size(); 
    } 
}; 

// and then we call sort on the container 
std::sort(container_name.begin(), container_name.end(), string_cmp());