ACMP Сортировка выбором

126

28 декабря 2021, 07:30

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

Задан массив целых чисел a0, a1, …, an−1.

Отсортируем его следующим образом:

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

Входные данные В первой строке входного файла INPUT.TXT задано одно целое число n (1 ≤ n ≤ 1000) — количество элементов в массиве. Во второй строке задано n целых чисел через пробел: a0, a1, …, an−1 (|ai| ≤ 109) — элементы массива.

Выходные данные В выходной файл OUTPUT.TXT выведите n чисел через пробел, где число i — это индекс первого максимального элемента на i-й фазе алгоритма.

Написал код, но он не работает.

int main()
{
    int n, imax = 0;
    int b[100];
    cin >> n;
    int *a = new int[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n - 1; i++)
        for(int j = i + 1; j < n; j++)
        if(a[j] < a[i])
    {
        imax = i;
        b[i]= imax;
        swap(a[i], a[j]);
    }
    for (int i = 0; i < n; i++)
        cout << b[i] << " ";

Answer 1

Зачем вам нужен массив b?

Сортировка выполняется так, как описано в условии. Комментарии показывают выполняемые шаги из описания:

int main()
{
    int n = 0;
    cin >> n;
    int* a = new int[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << "Indices: ";
    for (int i = n-1; i > 0; --i)  // У вас требование идти с конца
    {
        int idx = 0, max = a[0];
        for (int j = 1; j <= i; ++j)  // Ищем максимум
            if (max < a[j]) { idx = j; max = a[j]; } 
        // Выбирается только первый, потому что сравнение <, а не <=
        // Вывод индекса, обмен
        cout << idx << " ";
        swap(a[idx], a[i]);
    }
    cout << "\nSorted array: ";
    for (int i = 0; i < n; i++) cout << a[i] << " ";
}

Тут код в работе: https://ideone.com/9pytV4