0

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.
8
  • 2
    std::swap takes two arguments only. We know nothing about the swap you use. Commented Oct 21, 2021 at 17:18
  • What is the book & author? What is the page this code is from? Commented Oct 21, 2021 at 17:37
  • @Eljay Beginning c++17 from novice to profesional APRESS FIFTH EDITION Commented Oct 21, 2021 at 17:40
  • 1
    In the book, chapter 7, the Step 3 paragraph explains what the for loop is doing, and why there is a swap after the for loop. Commented Oct 21, 2021 at 17:47
  • @Eljay not sure where are you watching the exercise is in chapter 8, page 311. I understand why it's needed, I don't understand why it's placed where it placed ( outside the loop) doesn't make sense Commented Oct 21, 2021 at 18:12

1 Answer 1

1

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.

Sign up to request clarification or add additional context in comments.

7 Comments

thanks you explained it well @idz , I guess what I am still missing to grab the concept is only why the loop compare it always against "*words[start]" as this value is always the same ... if there a lot of words in the vector many times the comparison will result in false and no swap will happen ( swap within the loop)
That's the basic idea of QuickSort. You make a pass through the array, moving only the values less than some pivot... and then you do the same process on the new smaller sub arrays either side of the pivot. The wikipedia page explains it pretty well en.wikipedia.org/wiki/Quicksort
It's worthwhile working it out with pencil and paper for a few small arrays to get your head around how it works ;-)
thank you very much!!!
Integer division truncates the result so assuming this is the first round, start = 0, end = 3 and (start + end) / 2 == (0 + 3) / 2 == 3 / 2 == 1, so the value 2 (which has index 1) would be chosen [ 3, 2, 1, 4].
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.