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.
std::swaptakes two arguments only. We know nothing about theswapyou use.