Как возможно ускорить алгоритм?

272

12 мая 2022, 12:00

Написал программу, которaя в маcсиве из n целых чиcел наимeньший элeмент поставит на первое место, наименьший из оcтавшихся - на пoследнее, следующий по величине - на второе мeсто, cледующий - на предпоследнее и так далее - дo середины массива. Но проблема, что она очень медленная, и жрёт очень много памяти. Понимаю, что для программ такого масштаба это ничто, но хотелось узнать как можно решить это правильнее и лучше. Моя программа выполняет все тесты за 39 мс, и жрёт 2091 КiB, в то же время, лучшее решение выполняеться за 1 мс и берёт 532 KiB памяти.

#include <iostream>
using namespace std;
int main() {                     
    int n, j, i, mn= 32768;
    cin >> n;
    const int b = n;
    int* mass = new int[n + 1];
    for (i = 0; i <= n; i++)
    {
        mass[i] = 0;
    }
    for (int i = 0; i < n; i++)
    {
        cin >> mass[i];
    }
    j = n;
    i = 0;
    int F = 0;
    int I;
    while (i<n/2)
    {
        I = i;
            for (I; I < j; I++)
            {
                if (mass[I] < mn)
                {
                    mn = mass[I];
                    F = I;
                }
                else if (mass[I] == mn) F = I;
            }
            swap(mass[i], mass[F]);
            i++;
            mn = 32768;
            I = i;
            for (I; I < j; I++)
            {
                if (mass[I] < mn)
                {
                    mn = mass[I];
                    F = I;
                }
                else if (mass[I] == mn) F = I;
            }
            swap(mass[j - 1], mass[F]);
            j--;
            mn = 32768;
    }
    for (i = 0; i < n; i++)
    {
        cout << mass[i] << " ";
    }
    
}

Answer 1

Не уверен по поводу скорости, но как минимум код стал понятнее:

#include <iostream>
int findMinIndex(const int* arr, const int begin, const int end)
{
    int result = begin;
    for (int i = begin + 1; i < end; i++)
    {
        if (arr[i] < arr[result])
            result = i;
    }
    return result;
}
int main()
{
    using namespace std;
    int arr_size;
    cin >> arr_size;
    int* arr = new int[arr_size];
    for (int i = 0; i < arr_size; i++)
    {
        cin >> arr[i];
    }
    for (int i = 0, j = arr_size - 1; i < j; i++, j--)
    {
        swap(arr[i], arr[findMinIndex(arr, i, j + 1)]);
        swap(arr[j], arr[findMinIndex(arr, i + 1, j + 1)]);
    }
    
    // Debug output
    for (int i = 0; i < arr_size; i++)
        cout << arr[i] << "\t";
    cout << endl;
    return 0;
}