アルファベット順および文字長さの速さ

Question

私は現在かなり大きなテキストファイルを読み込み、アルファベット順および文字長でテキストファイルを並べ替えるプログラムを作成しています。私はこれを行うクイックソートを実装しました。私がquciksortingのために2つの方法を持っているということが、うまくいけば、いくつかの明確さを得るという問題があります。ここquickSortLenある一つは、彼らが必要なく、イムは、トラブル8月のような単語ので、両者を組み合わせることを有していると、コード

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); 
    } 

} 

と私はここにquickSortAlphを持っているよりは、その

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); 
} 
} 

仕事の両方のためのコードでありますブラボーよりもascii値が小さくなるだろうが、ブラボーの長さは8月よりも短い。どのように2つの組み合わせについて行くための任意の提案？

Answer 1

あなたは本当に自分のクイックソートを書く必要がありますか？あなたがしていない場合std::sortとカスタム比較functorを使用することができます。

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());