2

Сразу оговорюсь, я новичок в программирование и пока что знаниями в теории алгоритмов похвастаться не могу. Сегодня решал задачу сортировки массива состоящего из целочисленных элементов, который должен упорядочить в порядке убывания . Скажу честно, было тяжеловато решать эту проблему, пошел на принцип и не гуглил решение этой задачи. Что-то я написал, был близок, но все-таки чего-то не хватало. Решил погуглить и нашёл решение этой проблемы, удовлетворился тем, что мой код был схож с решением. Привожу код:

for (int j = 0; j < intArray.length; j++)
        for (int k = 0; k < intArray.length - 1; k++) {
            if (intArray[k] < intArray[k + 1]) {
                temp = intArray[k];
                intArray[k] = intArray[k + 1];
                intArray[k + 1] = temp;
            }
        }

Разберём пример. Допустим у нас есть массив целочисленных элементов (3, 2, 5, 1). После сортировки мы получим (5, 3, 2, 1). Пошагово это будет выглядеть так:

j = 0; k = 0; (3 < 2) --> false --> 3 2 5 1
       k = 1; (2 < 5) --> true  --> 3 5 2 1
       k = 2; (2 < 1) --> false --> 3 5 2 1

j = 1; k = 0; (3 < 5) --> true  --> 5 3 2 1
       k = 1; (3 < 2) --> false --> 5 3 2 1
       k = 2; (2 < 1) --> false --> 5 3 2 1

После второй итерации внешнего цикла, у нас уже есть готовый ответ, это достаточно для этого примера, но не для всех. Вопрос в следующем, почему внешний цикл должен управляться именно этим условием (j < intArray.length) ? Как понять, что для полного успеха, нужно именно такое условие? Просто хочется понять этот алгоритм изнутри... Спасибо за внимание.

2
  • Простой способ, добавить флаг, во внутреннем цикле при выполнении условия его сбрасывать, во внешнем цикле проверять, если не был сброшен, завершать внешний цикл досрочно.
    – dsnk
    24 сен 2015 в 18:20
  • Рекомендую ознакомится с Linq. Эта задача давно решена специалистами, по этому нет необходимости снова изобретать колесо. 24 сен 2015 в 19:21

3 ответа 3

5

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

То есть если у вас есть массив

{ 1, 2, 3, 4 }

то после первого прохода по массиву

{ 1, 2, 3, 4 }
 ^^^
{ 2, 1, 3, 4 }
    ^^^
{ 2, 3, 1, 4 }
       ^^^
{ 2, 3, 4, 1 }
          ^^^

в последней позиции массива будет находиться число 1.

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

Далее вам нет необходимости проходить по всему массиву, так как уже в последней позиции массива находится наименьший элемент.

Поэтому вам следует применить сортировку к массиву с числом элементов на единицу меньше, чем исходный массив, то есть к элементам

{ 2, 3, 4 }

Опять-таки 2 "всплывает" в самую крайнюю правую позицию, и вы получаете

{ 3, 4, 2, 1 }

и т.д.

Если массив уже отсортирован изначально, то нет никакой необходимости делать несколько проходов по массиву. Как определить, отсортирован массив или нет? Очень просто! если перестановок не было при проходе по массиву, то массив уже отсортирован.

Все эти рассуждения приводят к следующему коду

int last = intArray.length;

for ( boolean sorted = last == 0; !sorted; --last )
{
    sorted = true;
    for ( int i = 1; i < last; ++i )
    {
        if ( intArray[i-1] < intArray[i] )
        {                
            sorted = false;

            int tmp = intArray[i-1];
            intArray[i-1] = intArray[i];
            intArray[i] = tmp;
        }
    }               
}

Как вы можете видеть в этом коде

  • верхняя граница массива постоянно уменьшается по мере того, как наименьший элемент в под-массиве занимает крайне правую позицию

  • сортировка прекращается, как только обнаружено, что перестановок соседних элементов не было, то есть что массив уже является отсортированным.

4

Ваша реализация не оптимальна. Обратите внимание, что переменная j нигде не используется внутри цикла.
Должно быть примерно так:

for (int j = 0; j < intArray.Length - 1; j++)
{
    for (int k = j + 1; k < intArray.Length; k++)
    {
        if (intArray[j] < intArray[k])
        {
            int temp = intArray[k];
            intArray[k] = intArray[j];
            intArray[j] = temp;
        }
    }
}

А смысл пузырьковой сортировки такой: нужно пробежать все пары элементов массива и, при необходимости, поменять их местами. Поэтому j пробегает элементы 0 ... N-1, а k - элементы j+1 ... N, где N - индекс последнего элемента.

7
  • 3
    оптимальность квадратичных сортировок это вообще странное понятие :)
    – pavel
    24 сен 2015 в 19:07
  • @pavel я полностью согласен, однако, в данном случае, я лишь отметил неоптимальность реализации, не касаясь оптимальности самого подхода.
    – Dmitry D.
    24 сен 2015 в 20:49
  • 2
    @Аристарх В этом ответе представлен совершенно другой метод сортировки, а не тот, что вы используете в своем вопросе. Ваш метод - это метод пузырьковой сортировки, а метод, используемый в ответе - это ухудшенный метод сортировки выборкой. 24 сен 2015 в 23:45
  • 2
    @Аристарх Я назвал этот метод ухудшенным методом выборки, потому что в этой реализации постоянно происходит обмен текущего максимального элемента с большим элементом при каждом проходе по массиву, тогда как в базовом методе выборке обмен элемента происходит только один раз, когда максимальный элемент уже найден. 25 сен 2015 в 9:11
  • 2
    @Аристарх Вы должны понимать, что существуют разные методы сортировки. Пузырьковая сортировка и выборочная сортировка - это два различных метода. Но эффективность их в среднем одинакова и равна O( N^2).. 25 сен 2015 в 9:12
1

Сортировка массива по убыванию:

    int temp;
    for (int i = 0; i < array.length; i++) {
        for (int k = i + 1; k < array.length; k++) {
            if (array[i] < array[k]) {
                temp = array[i];
                array[i] = array[k];
                array[k] = temp;
            }
        }
    }

Ваш ответ

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

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