ACMP Sorting by Choice

In this task, you are asked to implement selection sorting.

An array of integers a0, a1, ..., an-1 is given.

Let's sort it as follows:

Select the largest element of the array and swap it with the last element (if the last one is the found maximum, then you can not make an exchange), exclude the last element from consideration, and if the length of the remaining section is greater than zero, go back to the previous item. So this one the algorithm consists of n phases, each of which selects a maximum. Your task is to implement this sorting in the described way and output n numbers-the indices of the maximum at each of the n phases. If the maximum occurs more than once, then you should always choose the first one.

Input data In the first line of the input file INPUT.TXT given a single integer n (1 ≤ n ≤ 1000) - the number of elements in the array. The second line contains n integers separated by a space: a0, a1,..., an-1 (|ai| ≤ 109) - array elements.

Output data To the output file OUTPUT.TXT print n numbers separated by a space, where the number i is the index of the first maximum element in the i-th phase of the algorithm.

I wrote the code, but it doesn't work.

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] << " ";
Author: Harry, 2019-12-15
Source

1 answers

Why do you need the b array?

Sorting is performed as described in the condition. The comments show the steps being performed from the description:

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] << " ";
}

Here is the code in the work: https://ideone.com/9pytV4

 3
Author: Harry, 2019-12-15 06:33:14