Sorting vector elements in descending order

Question

Please tell me what is wrong in my approach. When I run the code, it is taking too long to compute to see the result.

#include <iostream>
#include <vector>
using namespace std;

vector<int> vec;
vector<int> sort(vector<int> x) {
    vector<int> y;
    int i = 1;
    reset:for(i = 1; i <= x.size(); i++){
        for (int j = 1; j <= x.size();) {
            if (j == i) {
                j++;
            }
            else {
                if (x[i - 1] > x[j - 1]) {
                    j++;
                }
                else {
                    i++;
                    goto reset;
                }
            }
        }
        y.push_back(x[i - 1]);
        x.erase(x.begin() + i - 1);
    }
          return y;
}

int main(){
    vec.push_back(5);
    vec.push_back(9);
    vec.push_back(3);
    vec.push_back(6);
    vec.push_back(2);

    for (int i = 1; i <= vec.size(); i++) {
        cout << sort(vec)[i-1] << " ";
    }
}

I am sorting this given sequence of 5 integers into descending order. Please help.

My plan was to search for the greatest integer in the whole vector x and move to it to the vector y and repeat the process.

You're sorting the vector every time you want to print one element which can't help performance. — nitronoid
You increment i, then call goto reset; -> Where's that going to go, and what happens to i after the goto? — 1201ProgramAlarm
If it's taking too long, I assume you mean it never finishes and it's stuck in an infinite loop. Step through in a debugger and you'll see exactly what that loop is doing. — chris
Please see the edit for understanding what i was trying to do. — Akshit Bansal

Alecto Irene Perez Alecto Irene Perez · Accepted Answer · 2019-06-21T22:04:00

Simple bubble-sort example

I think that your sort function is entering an infinite loop because of the goto reset statement. If you want to implement a simple bubble-sort algorithm, you can do it like this:

#include <iostream>
#include <utility>
#include <vector>

void bubble_sort(std::vector<int>& v) {
    if(v.size() == 0) return; 

    for(int max = v.size(); max > 0; max--) {
        for(int i = 1; i < max; i++) {
            int& current = v[i - 1]; 
            int& next = v[i];
            if(current < next) 
                std::swap(current, next); 
        }
    }
}

This function takes a vector, and for every consecutive pair of elements in the vector, if they're out of order, it swaps them. This results in the smallest element "bubbling" to the top of the vector. The process is repeated until all the elements are in order.

If we test it, we see that it prints the right answer:

int main() {
    std::vector<int> test = {5, 9, 3, 6, 2}; 

    bubble_sort(test);

    for(int i : test) {
        std::cout << i << ' '; 
    }
    std::cout << '\n';
}

Using `std::sort` to do this faster

The standard library provides a sort function that'll sort pretty much anything. std::sort is really well implemented, it's more efficient than bubble sort, and it's really easy to use.

By default, std::sort orders things in ascending order, although it's easy to change it so that it works in descending order. There are two ways to do this. The first way sorts the vector using the reverse iterators (which allow you to pretend the vector is in reverse order), and the second way sorts the vector using std::greater, which tells std::sort to sort things in reverse order.

// Way 1:
std::sort(test.rbegin(), test.rend()); 

// Way 2:
auto compare_func = std::greater<>(); 
std::sort(test.begin(), test.end(), compare_func);

We can re-write the program using std::sort:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> test = {5, 9, 3, 6, 2}; 

    auto compare_function = std::greater<>(); 
    std::sort(test.begin(), test.end(), compare_function); 


    for(int i : test) {
        std::cout << i << ' '; 
    }
    std::cout << '\n';
}

Sorting vector elements in descending order

2 Answers

Simple bubble-sort example

Using std::sort to do this faster

Using `std::sort` to do this faster