Вывести индексы элементов массива до сортировки

Question

Отсортировать массив целых чисел X=(x1,x2,..,xn) по убыванию. Вывести индексы элементов первоначального массива в том порядке, который был у элементов первоначально. Вывести индекс самого большого и самого маленького элемента массива. Вот код: почему-то если искать максимальный и минимальный элементы массива до сортировки, то после нее в массив заполняется первым элементом. И как вывести индексы в первоначальном порядке? Заранее благодарю

   #include <iostream>
#include <stdlib.h>
#include <stdio.h>

void shellsort(int* a, int leng);

int main()
{
    int n, i, j = 0;
    printf("Enter size:\n");
    scanf_s("%d", &n);
    printf("Enter elements: \n");
    int* mas = new int[n];
    for (i = 0; i < n; i++)
    {
        scanf_s("%d", &mas[i]);
    }
    int max = mas[0];
    int d = 0;
    for (i = 0; i < n; i++)
    {
        if (max < mas[i])
        {
            mas[i] = max;
            d = i;
        }
    }
    printf("Max index is: %d\n", d);
    int min = mas[0];
    int e = 0;
    for (i = 0; i < n; i++)
    {
        if (min > mas[i])
        {
            mas[i] = min;
            e = i;
        }
    }
    printf("Min index is: %d\n", e);
    shellsort(mas, n);
    printf("\n");

    delete[]mas;
}

void shellsort(int* a, int leng)
{
    int k = 0, i, j, p, temp, step;
    int* gap = new int[leng];
    gap[0] = leng / 2;
    while (gap[k] > 1)
    {
        k++;
        gap[k] = gap[k - 1] / 2;
    }
    for (i = 0; i <= k; i++)
    {
        step = gap[i];
        for (j = step; j < leng; j++)
        {
            temp = a[j];
            p = j - step;
            while (p >= 0 && temp > a[p])
            {
                a[p + step] = a[p];
                p = p - step;
            }
            a[p + step] = temp;
        }
    }
    printf("\n");
    for (i = 0; i < leng; i++)
    {
        printf("%d", a[i]);
    }
}

Answer 1

Надеюсь, я правильно понял условие. Идея в том, чтобы хранить первоначальный индекс в одной структуре с элементом. Тогда при сортировке индексы будут расположены в нужном порядке.

#include <iostream>

void shellsort(std::pair<int, int>* a, int leng);

int main()
{
    int n, i, j = 0;
    std::cout << "Enter size:" << std::endl;
    std::cin >> n;
    std::cout << "Enter elements:" << std::endl;
    std::pair<int, int>* mas = new std::pair<int, int>[n];
    for (i = 0; i < n; i++)
    {
        std::cin >> mas[i].first;
        mas[i].second = i;
    }
    shellsort(mas, n);
    for (int i = 0; i < n; ++i) {
        std::cout << mas[i].first << " ";
    }
    std::cout << std::endl;
    for (int i = 0; i < n; ++i) {
        std::cout << mas[i].second << " ";
    }
    std::cout << std::endl;
    std::cout << "min ind: " << mas[n - 1].second << std::endl;
    std::cout << "max ind: " << mas[0].second;
    delete[] mas;
}

void shellsort(std::pair<int, int>* a, int leng)
{
    int k = 0, i, j, p, step;
    std::pair<int, int> temp;
    int* gap = new int[leng];
    gap[0] = leng / 2;
    while (gap[k] > 1)
    {
        k++;
        gap[k] = gap[k - 1] / 2;
    }
    for (i = 0; i <= k; i++)
    {

        step = gap[i];
        for (j = step; j < leng; j++)
        {
            temp = a[j];
            p = j - step;
            while (p >= 0 && temp.first > a[p].first)
            {
                a[p + step] = a[p];
                p = p - step;
            }
            a[p + step] = temp;
        }
    }
}

https://ideone.com/WFJCrq

БЛОГ НА HUSL

Вывести индексы элементов массива до сортировки

Ответы (1 шт):