Статья посвещена тому, как сортировать числовые массивы методом нахождения максимума или минимума и пузырьковой сортировки. Это рассмотрение основных алгоритмов сортировки, возможны и другие, но мы их рассмотрим в других статьях. Сортировать можно не только числа.

Алгоритмы - Алгоритмы Сортировки #1.

1. Нахождение Минимума.

1.1. Первое объяснение.

Найдите первое минимальное число, поменяйте его местами с первым и далее повторите процедуру до последнего, не брав во внимание первое число и так далее (потом не брав во внимание первое и второе, поменяв местами второе и минимальное в оставшемся массиве, если оно меньше, потом первое, и второе, и третье и т.д.). Это алгоритм сортировки от меньшего к большему. Переставляйте на последнее место, если хотите получить алгоритм от большего к меньшему.

1.2. Второе объяснение.

Первого объяснения (1.1. Первое объяснение.) достаточно для тех, кто уже знает этот алгоритм, теперь рассмотрим алгоритм сортировки нахождением минимума от меньшего к большему подробнее:

1. Введите временную переменную index для запоминания текущего значения номера элемента массива.
2. Выполните цикл N раз, где N равно размеру массива минус единица. Введите переменную i для количества уже проанализированных элементов - это счётчик цикла. Объявите её для начала алгоритма на начало массива:
- 2.1. Присвойте переменной index значение i.
- 2.2. Выполните цикл от i+1 до конца массива, где j счётчик этого цикла. Далее массив будем называть arr, а доступ к i-тому элементу будем называть arr[i]:
  - 2.2.1. Если arr[index] больше j-того элемента (arr[index] > arr[j]), то присвойте переменной index начение счётчика j, index:=j.
- 2.3. Обменяйте местами значения элементов массива с индексами. index и i.
Конец.

Далее рассмотрим блок-схему алгоритма, т.к. в алгоритме не учтено присвоение счётчиков цикла:

Входные данные: arr — входной сортируемый массив.

Рис. 1. Блок-схема алгоритма сортировки нахождением минимума от меньшего к большему.

Также возможен алгоритм сортировки от большего к меньшему, но с другими параметрами.

1.3. Третье объяснение.

Теперь рассмотрим алгоритм сортировки от меньшего к большему нахождением минимума на языке Java:

private static void sortArrMin(ArrayList<Integer> arr) {
    // 1. Введите временную переменную index для запоминания текущего значения номера элемента массива.
    int index;

    // Введём переменную для обмена, запомните сортировать можно не только числа.
    Integer temp;

    // 2. Выполните цикл N раз, где N равно размеру массива минус единица. Введите переменную i для количества уже проанализированных элементов - это счётчик цикла. Объявите её для начала алгоритма на начало массива:
    for(int i = 0; i < arr.size() - 1; i++) {

        // 2.1. Присвойте переменной index значение i.
        index = i;

        // 2.2. Выполните цикл от i+1 до конца массива, где j счётчик этого цикла. Далее массив будем называть arr, а доступ к i-тому элементу будем называть arr[i]:
        for(int j = i + 1; j < arr.size(); j++ ) {

            // 2.2.1. Если arr[index] больше j-того элемента (arr[index] > arr[j]), то присвойте переменной index начение счётчика j, index:=j.
            if(arr.get(index) > arr.get(j)) index = j;

        }

        // Обменяйте местами значения элементов массива с индексами. index и i.
        temp = arr.get(index);
        arr.set(index, arr.get(i));
        arr.set(i, temp);
    }

}

2. Нахождение Максимума.

2.1. Первое объяснение.

Алгоритм нахождения максимального элемента эквивалентен алгоритму сортировки нахождения минимального элемента, только имеет обратный смысл сортировка от большего к меньшему и от меньшего к большему.

Найдите первое максимальное число, поменяйте его местами с первым и далее повторите процедуру до последнего, не брав во внимание первое число и так далее (потом не брав во внимание первое и второе, поменяв местами второе и максимальное в оставшемся массиве, если оно больше, потом первое, и второе, и третье и т.д.). Это алгоритм сортировки от большему к меньшему. Переставляйте на последнее место, если хотите получить алгоритм от меньшего к большему.

2.2. Второе объяснение.

Первого объяснения (2.1. Первое объяснение.) достаточно для тех, кто уже знает этот алгоритм, теперь рассмотрим алгоритм сортировки нахождением максимума от меньшего к большему подробнее:

1. Введите временную переменную index для запоминания текущего значения номера элемента массива.
2. Выполните цикл N раз, где N равно размеру массива минус единица. Введите переменную i для количества уже проанализированных элементов - это счётчик цикла. Объявите её для начала алгоритма на конец массива:
- 2.1. Присвойте переменной index значение i.
- 2.2. Выполните цикл от 0 до размер массива - i, где j счётчик этого цикла. Далее массив будем называть arr, а доступ к i-тому элементу будем называть arr[i]:
  - 2.2.1. Если arr[index] меньше j-того элемента (arr[index] < arr[j]), то присвойте переменной index начение счётчика j, index:=j.
- 2.3. Обменяйте местами значения элементов массива с индексами. index и размер массива - i.
Конец.

Далее рассмотрим блок-схему алгоритма, т.к. в алгоритме не учтено присвоение счётчиков цикла:

Входные данные: arr — входной сортируемый массив.

Рис. 2. Блок-схема алгоритма сортировки нахождением максимума от меньшего к большему.

Также возможен алгоритм сортировки от большего к меньшему, но с другими параметрами.

2.3. Третье объяснение.

Теперь рассмотрим алгоритм сортировки от меньшего к большему нахождением максимума на языке Java:

private static void sortArrMax(ArrayList<Integer> arr) {
    // 1. Введите временную переменную index для запоминания текущего значения номера элемента массива.
    int index;

    // Введём переменную для обмена, запомните сортировать можно не только числа.
    Integer temp;

    // 2. Выполните цикл N раз, где N равно размеру массива минус единица. Введите переменную i для количества уже проанализированных элементов - это счётчик цикла. Объявите её для начала алгоритма на конец массива:
    for(int i = arr.size() - 1; i >= 0; i--) {

        // 2.1. Присвойте переменной index значение i.
        index = i;

        // 2.2. Выполните цикл от 0 до i-1, где j счётчик этого цикла. Далее массив будем называть arr, а доступ к i-тому элементу будем называть arr[i]:
        for(int j = i - 1; j >= 0; j-- ) {

            // 2.2.1. Если arr[index] больше j-того элемента (arr[index] > arr[j]), то присвойте переменной index начение счётчика j, index:=j
            if(arr.get(index) < arr.get(j)) index = j;

        }

        // Обменяйте местами значения элементов массива с индексами. index и i.
        temp = arr.get(index);
        arr.set(index, arr.get(i));
        arr.set(i, temp);
    }

}

3. Пузырьковая Сортировка.

3.1. Первое объяснение.

Объяснение на примере пузырьковой сортировки от меньшего к большему:

Берём последний элемент и стравнивываем его с предпоследним, если последний меньше больше предыдущего, то меняем их местами. Применяем данное правило к новому предпослениму элементу и элементу, расположенному перед предпосленим. Повторяем это правило до первого элемента. Снова повторяем это правило, считая, что первый элемент трогать не надо, т.к. на его место правило протолкнуло наименьший элемент. Теперь в результате этого правила протолкулся на второе место наименьший элемент в оставшейся части. Повторяем это правило проталкивания обменом к оставшейся части массива, исключив первый и второй. И так далее, пока не осортируется массив. Посмотрим на это правило (пузырьковую сортировку) на Анимации 1. Пузырьковая сортировка на обратно отсортированном массиве:

Анимация 1. Пузырьковая сортировка на обратно отсортированном массиве (применённая к обратному случаю (обратным входным данным)).

3.2. Второе объяснение.

Первого объяснения (3.1. Первое объяснение.) достаточно для тех, кто уже знает этот алгоритм, теперь рассмотрим алгоритм пузырьковой сортировки от меньшего к большему подробнее:

1. Введите временную переменную temp для запоминания текущего значения элемента массива.
2. Введём цикл для перемещения пузырьков, равный по повторениям (Размер массива arr).:
- 2.1. Просмотрим в цикле все элементы массива, просматриваются два элемента, поэтому повторений будет (Размер массива - 1). Элементы просматриваются с конца.
  - 2.1.1. Вычислим индекс предыдущего элемента за анализируемым.
  - 2.1.2. Если текущий элемент больше предыдущего за ним, то меняем их местами.
Конец.

Далее рассмотрим блок-схему алгоритма, т.к. в алгоритме не учтено присвоение счётчиков цикла:

Входные данные: arr — входной сортируемый массив.

Рис. 3. Блок-схема алгоритма сортировки пузырьком от меньшего к большему.

3.3. Третье объяснение.

Теперь рассмотрим алгоритм сортировки пузырьком от меньшего к большему на языке Java:

private static void sortArrBuble(ArrayList<Integer> arr) {

    // 1. Введите временную переменную temp для запоминания текущего значения элемента массива.
    Integer temp;

    // 2. Введём цикл для перемещения пузырьков, равный по повторениям (Размер массива arr).
    for(int i = 0; i < arr.size() - 1; i++)
    {

        // 2.1. Просмотрим в цикле все элементы массива, просматриваются два элемента, поэтому повторений будет (Размер массива - 1). Элементы просматриваются с конца.
        for(int j = arr.size() - 1; j > i; j--)
        {

            // 2.1.1. Вычислим индекс предыдущего элемента за анализируемым.
            int decJ = j - 1;

            // 2.1.2. Если текущий элемент больше предыдущего за ним, то меняем их местами.
            if(arr.get(j).intValue() < arr.get(decJ).intValue()) {

                // Меняем их местами.
                temp = arr.get(j);
                arr.set(j, arr.get(decJ));
                arr.set(decJ, temp);

            }
        }
    }
}

4. Заключение.

Мы рассмотрели 3 алгоритма сортировки, как видно, у них одинаковая сложность.

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