Проблема с пониманием алгоритма сортировки

Question

Проблема с пониманием алгоритма сортировки

Рейтинг: 0Ответов: 1Опубликовано: 02.05.2023

Я написал сортировку динамического массива по убыванию количества отрицательных элементов в нём, но не понимаю, почему во вложенном цикле по j мы отнимаем от n переменную i. Написал комментарий в строке, не уверен, правильно ли это. Объясните, пожалуйста.

P.S в данном случае n - кол-во столбцов, динамический массив заполнен выше, прикреплять его не вижу смысла, поскольку вопрос именно теоретический. Спасибо!

void Arr_sort() {

    double* key = new double[n];
    int counter = 0;
    for (int j = 0; j < n; j++) 
    {


        for (int i = 0; i < m; i++)
        {

            if (arr[i][j] < 0) 
            {
                counter++;
                

            }
        }

        key[j] = counter;
    }

    for (int i = 0; i < n - 1; i++)
    {

        for (int j = 0; j < n - i - 1; j++) //Вот эта строка. Я подумал, что мы вычитаем из кол-ва столбцов те, что уже прошли 
        {

            if (key[j] < key[j + 1]) 
            {

                swap(key[j], key[j + 1]);

c# сортировка динамические-массивы

Источник: Stack Overflow на русском

Answer 1

▲ 0

Дабы избежать недопонимания, распишу все немного подробнее.

Вы представили алгоритм сортировки пузырьком (по убыванию), он работает следующим образом:

Переместить самый маленький элемент в конец массива
Переместить самый маленький элемент из оставшихся (2-й минимум) на предпоследнее место
Сделать (всего) L - 1 повторений, где L - длинна массива

Отсюда вытекает возможность оптимизации: если мы уже переместили самый маленький элемент в конец, то в момент когда 2-й минимум достигает своего предпоследнего места, уже нет надобности проверять, не больше ли он следующего (в данном случае последнего) элемента, поскольку первым пунктом мы гарантируем, что последний элемент уже самый маленький, т.е. заведомо меньше текущего. Это же верно и для всех следующих итераций.

Именно для такой оптимизации и нужно вычитать из n количество совершенных итераций i. Например на первой итерации (i = 0) n - i будет равен n, т.е. мы обходим весь массив. На второй итерации (i = 1) n - i уже будет равно n - 1, что и вызовет пропуск излишней обработки последнего элемента.

Таким образом мы действительно "вычитаем из кол-ва столбцов те, что уже прошли", если вы имели ввиду то же, что и я.

Проблема с пониманием алгоритма сортировки

Ответы