Please could you help me to understand the below code from a book?

I am wondering why " swap(words, start, current); " is not part of the for loop within the below code?

The final effect of the "for loop - check words against chosen word" should be to position all the words less than the chosen word before all the words that are greater than or equal to it.

However, without swapping the "start" and the "current" after each I iteration,I don't understand how the comparison is done as "*words[i]" within the IF statement will always compare against the "*words[start]" which is always equal to index = 0 ( condition is iterated within the loop, meaning comparison is done always against the 0 index)

// referring to "*words[i] < *words[start]")

P.s. my initial assumption was that the swap line "swap(words, start, current);" should be part of the for loop, below as you can see it's not part of the loop but rather out of the for loop.

void sort(Words& words, size_t start, size_t end)
{
  // start index must be less than end index for 2 or more elements

  if (!(start < end))
    return;

  // Choose middle address to partition set

  swap(words, start, (start   end) / 2);

// Check words against chosen word

size_t current {start};
for (size_t i {start   1}; i <= end; i  ) 
  {
    if (*words[i] < *words[start])
      swap(words,   current, i);
  }
  swap(words, start, current);

  if (current > start) sort(words, start, current - 1);
  if (end > current   1) sort(words, current   1, end);
}

Below adding also the code defined for swap function ( in case you think it's relevant)

#include <iostream>
#include <iomanip>
#include <memory>
#include <string>
#include <string_view>
#include <vector>

using Words = std::vector<std::shared_ptr<std::string>>;
void swap(Words& words, size_t first, size_t second);
void sort(Words& words);
void sort(Words& words, size_t start, size_t end);
void extract_words(Words& words, std::string_view text, std::string_view separators); void show_words(const Words& words);
size_t max_word_length(const Words& words);

int main() 
{
  Words words;
  std::string text;       
  const auto separators{" ,.!?\"\n"}; 

std::cout << "Enter a string terminated by *:" << std::endl;    getline(std::cin, text, '*');

extract_words(words, text, separators); 
if (words.empty())
 {
std::cout << "No words in text." << std::endl;
return 0;
 }
sort(words);
show_words(words);
}

void extract_words(Words& words, std::string_view text, std::string_view separators) 
{
size_t start {text.find_first_not_of(separators)};
size_t end {};

while (start != std::string_view::npos) 
 {
 end = text.find_first_of(separators, start   1); 
 if (end ==    std::string_view::npos)
 end = text.length();
words.push_back(std::make_shared<std::string>(text.substr(start, end - start)));
 }
}


void swap(Words& words, size_t first, size_t second)
{
  auto temp{words[first]};
  words[first] = words[second];
  words[second] = temp; 
}

This just swaps the addresses in words at indexes first and second.

CodePudding user response：

What's going on is that the middle value of the array is being chosen as the pivot value and move "out of the way" to the start of the array:

swap(words, start, (start   end) / 2);

The loop then process all values from start 1 to end inclusive so that once it is complete all values from start to current inclusive are less than the pivot value. Note the loop is from start 1 so we never change the pivot value.

size_t current {start};
for (size_t i {start   1}; i <= end; i  ) 
  {
    if (*words[i] < *words[start])
      swap(words,   current, i);
  }

But, at this point the pivot is in the wrong place. For the recursive calls to work the value at words[current] must be contain the pivot value. So it needs to be swapped from where we put it (words[start]) to current

swap(words, start, current);

It may be useful to think about what would happen if you were sorting an simple, small array like

[3,2,1]

You choose the middle value and move it to the start...

[2,3,1]

You move all values less than the pivot...

[2,1,3]
   ^
   |
current

You move the pivot back into place

[1,2,3]

You sort the portion before current, [1], and after current [3] which involves no change since they are single elements.

Notice that if you had not moved the pivot into the correct place, sorting the subarrays would not yield the correct answer.