Решение задачи Сортировка выбором с Acmp

Без пояснения   Просмотров: 68


В этой задаче вам предлагается реализовать сортировку выбором.

Задан массив целых чисел a0, a1, …, an−1. Отсортируем его следующим образом:

выберем наибольший элемент массива и поменяем его местами с последним элементом (если последний и есть найденный максимум, то обмен можно не совершать),
исключим из рассмотрения последний элемент и если длина оставшегося участка больше нуля перейдем опять к предыдущему пункту.
Таким образом, этот алгоритм состоит их n фаз, на каждой из которых выбирается максимум. Ваша задача реализовать эту сортировку описанным способом и вывести n чисел — индексы максимума на каждой из n фаз. Если максимум встречается более одного раза, то надо всегда выбирать первый из них.

Код

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    vector<int> t = a;
    sort(t.begin(), t.end());
    for(int i = t.size() - 1; i >= 0; --i){
        for(int j = 0; j < a.size(); ++j)
            if(a[j] == t[i]){
                cout << j << " ";
                a[j] = a[a.size() - 1];
                a.erase(a.begin() + a.size() - 1);
                break;
            }
    }
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться