CODEWITHSUNDEEP
c++algorithmsortingquicksort
Mustafa Süve
Mustafa Süve

Reputation: 151

C++ gives different outputs for almost the same code

I have some lines of a book shuffled and their words are shuffled too. I want to sort them using quicksort algorithm. I sorted the lines and it worked well. then I tried to sort each line like this;

for each (Line l in lines) {
    srand(255);
    l.quicksort(0, l.words.size() - 1);
    for each (Word w in l.words)
        cout << w.content << " ";
    cout << endl;
}

srand part is because I am using randomized quick sort. This loop gives me the correct results. However, when I tried to write it again like this;

for each (Line l in lines) {
    for each (Word w in l.words)
        cout << w.content << " ";
    cout << endl;
}

It gives an output like I didn't call the quicksort function. It is the same code with one line missing. Why is it happening?

Line class:

#include<iostream>
#include<vector>
#include "word.h"
using namespace std;

class Line {
public:
    vector<Word> words;
    Line(string&, string&);
    void quicksort(int, int);
private:
    int partition(int, int);
    void swap(int, int);
};

Line::Line(string& _words, string& orders) {
    // Reading words and orders, it works well.
}

void Line::quicksort(int p, int r) {
    if (p < r) {
        int q = partition(p, r);
        quicksort(p, q - 1);
        quicksort(q + 1, r);
    }
}

int Line::partition(int p, int r) {
    int random = rand() % (r - p + 1) + p;
    swap(r, random);
    int x = words[r].order;
    int i = p - 1;
    for (int j = p; j < r; j++)
        if (words[j].order <= x) {
            i++;
            swap(i, j);
        }
    swap(i + 1, r);
    return i + 1;
}

void Line::swap(int i, int j) {
    if (i != j) {
        Word temp = words[j];
        words[j] = words[i];
        words[i] = temp;
    }
}

Upvotes: 0

Views: 255

Answers (1)

Jarod42
Jarod42

Reputation: 217283

You sort a local copy, iterate by reference instead:

srand(255); // Call it only once (probably in main)
for (Line& l : lines) {
    l.quicksort(0, l.words.size() - 1);
    for (const Word& w : l.words)
        std::cout << w.content << " ";
    std::cout << std::endl;
}
// Second loop
for (const Line& l : lines) {
    for (const Word& w : l.words)
        std::cout << w.content << " ";
    std::cout << std::endl;
}

Upvotes: 2

Related Questions