Quicksorting alphabetically and by character length

Question

I am currently writing a program that reads a pretty large text file and sorts the text file alphabetically and by character length. i implemented a quicksort to do this. the problem that im having and hopefully will get some clarity on is that i have two methods for quciksorting. One which is quickSortLen here is the 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);
  }

}

and than i have quickSortAlph here is the code for that

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

both work as they should but im having trouble combining the two because a word like august is going to have a less ascii value than bravo but the length is of bravo is less than august. any suggestions on how to go about combining the two?

I'm assuming this uses the typical dictionary organization of only sorting by length when the words are identical for all characters of the shorter word. If that's the case, then how about creating a new vector of only words that need to be sorted by length and passing that vector into `quickSortLen`. i.e. Instead of passing the entire dictionary into quicksortByLen, only pass in a vector containing "abs", "absolute", "absolutely". — bpgeck, Oct 16 '15 at 19:31
@bpgeck: the standard string comparison routine will take care of that. There is *no* way it can consider `abs` greater or equal to `absolute`. — Jongware, Oct 16 '15 at 19:38
So how *should* "august" and "bravo" compare? You have two very different requirements, entirely incompatible to each other. — Jongware, Oct 16 '15 at 19:40
bravo should be before august in the vector. its suppose to be by alphabetized by length — Nathaniel OToole, Oct 16 '15 at 20:06
@NathanielOToole - So the title should be sorting by length and then alphabetically? If sorting an array of pointers to words, and if you're allowed to use a second temp array of pointers for merge sort, the merge sort might be faster because it does more moves (of pointers) but fewer compares (of the words). — rcgldr, Oct 16 '15 at 22:40

score 4 · Answer 1 · edited May 23 '17 at 12:23

4

Do you really need to write your own quick sort? If you don't the you could use std::sort with a custom compare 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());

edited May 23 '17 at 12:23

Community

1
1

answered Oct 16 '15 at 19:35

NathanOliver

171,901
28
288
402

I do have to implement our own sorting algorithm – Nathaniel OToole Oct 16 '15 at 20:07
You can still use this as the comparison instead of doing two sorts. – stark Oct 16 '15 at 20:34
Since you aren't storing state with your `string_cmp` functor you could implement it as a lambda and it'd be faster. – Casey Oct 16 '15 at 22:06
@Casey I am not sure if it would or would not since a lambda is basically an inline functor and the compiler still stamps out a class for it. I would think the final code would be very close. – NathanOliver Oct 16 '15 at 22:12
@rcgldr I am already doing that. if the sizes are equal I compare the strings alphabetical. otherwise I return a comparison of the sizes. – NathanOliver Oct 16 '15 at 22:46
@NathanOliver - You're correct, I messed up an edit on my prior comment, which should have only asked if that is what the OP really wanted. I'll delete this comment in a bit. – rcgldr Oct 16 '15 at 22:51

Quicksorting alphabetically and by character length

1 Answers1