-1

I have to sort the array of struct by using a QuickSort algorithm(not built-in function, i have to write it manually) and also take the measure of working time and compare with standard C++ sort function. After i compile my code the output file(sort.txt) looks the same. What have i done wrong?

struct Info
{
    int Birth;
    char Name[20];
    char SurName[25];
};

template <keys T>
struct Comparer {

    bool operator ()(const Info &m1, const Info &m2) const {

        return (T == YEAR ? m1.Birth > m2.Birth : strcmp(m1.Name, m2.Name) > 0);
    }

};

int partition(vector<Info> &vArray, int start, int end) {
    int pivotValue, pivotIndex, mid;

    mid = (start + end) / 2;
    swap(vArray[start].Birth, vArray[mid].Birth);
    swap(vArray[start].Name, vArray[mid].Name);
    swap(vArray[start].SurName, vArray[mid].SurName);


    pivotIndex = start;
    pivotValue = vArray[start].Birth;

    for (int scan = start + 1; scan <= end; scan++) {
        if (vArray[scan].Birth < pivotValue) {
            pivotIndex++;
            swap(vArray[pivotIndex].Birth, vArray[scan].Birth);
            swap(vArray[pivotIndex].Name, vArray[scan].Name);
            swap(vArray[pivotIndex].SurName, vArray[scan].SurName);

        }
    }

    swap(vArray[start].Birth, vArray[pivotIndex].Birth);
    swap(vArray[start].Name, vArray[pivotIndex].Name);
    swap(vArray[start].SurName, vArray[pivotIndex].SurName);
    return pivotIndex;
}

template <keys T>
void quickSort(vector<Info>&vArray, int start, int end) {
    int pivotPoint;
    if (start < end) {

        pivotPoint = partition(vArray, start, end);

        quickSort<T>(vArray, start, pivotPoint - 1);

        quickSort<T>(vArray, pivotPoint + 1, end);
    }
}

void Print(const vector<Info> Mas)
{
    string path = "sort.txt";
    ofstream Out;
    Out.open(path);
    if (!Out.is_open()) {
        cout << "wdw" << endl;

    }
    else  {
        for (int i = 0; i < (int)Mas.size(); i++)
            Out << Mas[i].Name << " " << Mas[i].SurName << " " << Mas[i].Birth << "\n";
    }
    Out.close();
}

template<keys T>
bool isSorted(vector<Info> Mas)
{
    Comparer<T> c;
    for (int i = 0; i < Mas.size() - 1; i++)
        if (c(Mas[i], Mas[i + 1]))
            return false;
    return true;
}

In main function:

        quickSort<YEAR>(Mas, 0, pow(rows, i));

    Print(Mas);

My full code: https://www.codepile.net/pile/e2z3l7E0

Names.txt and Surnames.txt to generate: https://dropmefiles.com/riOmD

karver35
  • 31
  • 1
  • 7
  • 2
    Apart from the obvious bug that I pointed out in my answer. Get used to making a [mcve] when you ask questions. What is `keys` in `template ` for example? – Ted Lyngmo Nov 21 '19 at 16:23
  • Thanks for your answer. So thr key is YEAR in my case. – karver35 Nov 21 '19 at 17:14
  • 1
    What type is `keys`? Don't make us quess. Put enough code in the question for others to be able to compile it. – Ted Lyngmo Nov 21 '19 at 17:24
  • You can find my full code here codepile.net/pile/qAKEJ4XK – karver35 Nov 21 '19 at 17:45
  • 1
    That's not how it's working. People are rarely willing to read through a lot of working code to find the part that is failing. Especially when you use non-standard things like `conio.h` etc. Not many can compile that code. You are supposed to post the smallest piece of code needed for people to help you here. Create a [mcve] out of your full code. Check that it also fails - and put _that_ code in the question. If you are unsure if you've included non-standard parts, use a [good online compiler](https://godbolt.org/z/HMPYJM) and try compiling it there before updating your question. – Ted Lyngmo Nov 21 '19 at 18:39
  • Btw, I just glanced at your full code and noticed it still has the bug I pointed out in my answer. – Ted Lyngmo Nov 21 '19 at 18:40
  • It's quite strange but when i swap start and end in main quickSort(Mas, 0, 10000); It shows that vector is out of range. – karver35 Nov 22 '19 at 01:39
  • 1
    That's because you have more than one bug. You do understand that by calling it like this: `quickSort(Mas, 100000, 0);` there will be **no** sorting? `start` is `>` than `end` so the condition in the `if` statement will be `false`. Right? How many elements do you have i `vector Mas`? Make a [mcve] so that we can compile the same code as you and this will probably be solved quickly. – Ted Lyngmo Nov 22 '19 at 06:38
  • Minimal reproducible example depends on IDLE you using. Also i use Generate function with .txt files(names,surnames) for generation an unsorted file Data.txt. So now i have reduced my code as it possible. You can check it here: https://www.codepile.net/pile/xRBp036k – karver35 Nov 22 '19 at 10:26
  • 1
    That's not a [mcve] unless you suspect that the code that fails has anything to do with the non-standard `` functions etc. The `` parts making timings isn't part of a minimal example either. Make it compile with a standard compiller, https://godbolt.org/z/KdncC- then [edit](https://stackoverflow.com/posts/58979156/edit) the question and put that code in there. – Ted Lyngmo Nov 22 '19 at 11:41
  • 1
    You should also turn on more warnings. You have a lot of conversions between types, `unsigned` and `signed`, `floats` and `int`s. That's usually not a good sign. When you loop an index varianble, instead of casting the return value from the `size()` function to an `int`, declare your index variable as `size_t` or `auto`. – Ted Lyngmo Nov 22 '19 at 11:47
  • 1
    And what is `swapChar(*vArray[start].Name, *vArray[mid].Name);` doing do you think? Did you test it? It swaps the first character in the character arrays. – Ted Lyngmo Nov 22 '19 at 11:58
  • Thank you so much for advice. My entire code is based on this algorithm :https://stackoverflow.com/questions/40730549/sorting-swapping-elements-of-vector-of-structs-for-quicksort-algorithm-c – karver35 Nov 22 '19 at 13:07
  • You are welcome! Please see my additions to my answer too. Found some bugs that need attention :-) Btw, use the standard swap function: `std::swap(vArray[start].Name, vArray[mid].Name);`.for swapping. You don't need to write your own. – Ted Lyngmo Nov 22 '19 at 13:08
  • Did you also read [this link](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c) in the comments? It's very long but has a lot of good stuff in it. – Ted Lyngmo Nov 22 '19 at 14:00
  • 1
    Not yet, but thanks for your time. Sure to read this later. – karver35 Nov 22 '19 at 15:06
  • Have you compiled my code succeed? – karver35 Nov 28 '19 at 03:16
  • Yes, but as I mention in my answer, it has some bugs that I point out. Here's what I compiled https://godbolt.org/z/ftKsZB I've made a lot of changes, but not fixed your bugs. If you use `g++` or `clang++` compile with the `-fsanitize=undefined -fsanitize=address` options to see the error more clearly. – Ted Lyngmo Nov 28 '19 at 07:17
  • I have just complied your suggested option and got "vector out of range" error. I checked again the entire code. Can`t really find the issue and solution. – karver35 Nov 28 '19 at 15:19
  • The code I shared still has the bug I pointed out in my answer: "_`vArray[1]` is illegal when `vArray.size()` is `1`_". Did you compile with the suggested options? Did you see the added output that shows that you are indexing the vector out of range (as I mentioned in my answer)? – Ted Lyngmo Nov 28 '19 at 15:46
  • I assume when vArray.size() is 1 only vArray[0] is legal. Is it correct? – karver35 Nov 30 '19 at 16:58
  • That's correct. `[0, size())` is the valid subscript operator range. – Ted Lyngmo Nov 30 '19 at 17:14
  • Any ideas how to solve this? – karver35 Dec 02 '19 at 13:25
  • You'll have to make changes in the implementation of the algorithm you are using to not do indexing out of bounds. One option could be to use `std::sort` instead of implementing quicksort based on code that you don't fully understand. Or make the implementation yourself from start. In that case everything should be fully understood. – Ted Lyngmo Dec 02 '19 at 14:09
  • Thanks for the tip, but the goal of the program was to write my own sorting function and implement it for a vector of structs – karver35 Dec 02 '19 at 14:11
  • Then I think you would be better off writing it from scratch, following some pseudo code examples like [this](https://en.wikipedia.org/wiki/Quicksort). – Ted Lyngmo Dec 02 '19 at 14:14

1 Answers1

1

These parts guarantees that no sorting will be done:

if (start < end) { 
//... do the sorting
} // else don't

//                   start  end                      
quickSort<YEAR>(Mas, 100000, 0);

In your partition() function, you could add some debug prints to get you on the right track:

    int pivotValue, pivotIndex, mid;

    mid = (start + end) / 2;
    std::cout << "size: " << vArray.size() << " start: " << start << " mid: " << mid
              << " end: " << end << "\n";
    // ...

    for (int scan = start + 1; scan <= end; scan++) {
        std::cout << "scan: " << scan << "\n";
        // ...

What you will notice is that you are actually indexing out of bounds:

size: 1 start: 0 mid: 0 end: 1
scan: 1

vArray[1] is illegal when vArray.size() is 1 so the program has undefined behaviour.

Your Info has a char Name[10] member which means that only names up to 9 characters long can be stored in it. Your names.txt file contains 59 names that are longer. You will therefor write out of bounds, probably into the following SurName member.

Ted Lyngmo
  • 93,841
  • 5
  • 60
  • 108