1

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

Задан массив целых чисел 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] << " ";
1
  • Отредактируйте вопрос, внеся код туда.
    – MBo
    Commented 15 дек. 2019 в 6:11

1 ответ 1

4

Зачем вам нужен массив 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

5
  • Ввел imax чтоб запоминать на каком i максимальный элемент, а массив второй чтоб туда записывать , думал что так будет легче.
    – Jool
    Commented 15 дек. 2019 в 6:36
  • Про imax я вопрос снял :)
    – Harry
    Commented 15 дек. 2019 в 6:40
  • Есть маленькая проблема он выводит на один индекс меньше чем в массиве
    – Jool
    Commented 15 дек. 2019 в 6:40
  • На последнем шагу мы уже ничего не проверяем - очевидно, что последний элемент на своем месте и так - после того как расставлены все остальные. Если очень хочется - добавьте перед выводом "Sorted array" вывод нуля :)
    – Harry
    Commented 15 дек. 2019 в 6:42
  • Все стало понятно :) ! Спасибо)
    – Jool
    Commented 15 дек. 2019 в 6:46

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.