Урок 5

Алгоритмы

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

1. Вычисление среднего арифметического

Начнем с нахождения среднего арифметического элементов массива. Сначала в цикле переберем все элементы массива и вычислим их сумму. После чего разделим сумму на длину массива:

Пример 1. Вычисление среднего арифметического

public class Average {
    public static void main(String[] args) {
        double[] nums = {10.1, 11.2, 12.3, 13.4, 14.5};
        double result = 0;

        for (double d : nums) {
            result += d;
        }
        System.out.println("Среднее арифметическое " + result / nums.length);
    }
}

2. Обмен значениями

Часто в процессе решения той или иной задачи, две переменные должны обменяться значениями. Есть два варианта решения этой задачи:

Вариант 1: обмен значениями с использованием временной переменной

Вводим временную переменную, которая на время придержит значение из одной переменной:

int tmp = a;
a = b;
b = tmp;

Пример 2. Обмен значениями с использованием временной переменной

public class ChangeValues1 {
    public static void main(String[] args) {
        int a = 3;
        int b = 5;

        int tmp = a;
        a = b;
        b = tmp;

        System.out.println("a = " + a);
        System.out.println("b = " + b);
    }
}

Вариант 2: обмен значениями без использования временной переменной

Третья переменная не вводится, обмен достигается путем сложения и вычитания:

a = a + b;
b = a - b;
a = a - b

Пример 3. Обмен значениями

public class ChangeValues2 {
    public static void main(String[] args) {
        int a = 3;
        int b = 5;

        a = a + b; // a = 8, b = 5
        b = a - b; // a = 8, b = 3
        a = a - b; // a = 5, b = 3

        System.out.println("a = " + a);
        System.out.println("b = " + b);
    }
}

3. Инвертирование массива

Существует массив {1, 2, 3, 4} и его надо развернуть (или инвертировать) и получить массив {4, 3, 2, 1}.

Пример 4. Инвертирование массива

Находим середину массива - array.length / 2. Перебираем элементы массива от начала до середины и одновременно меняем местами элементы с индексом i и array.length - i - 1. Для обмена значениями используем вариант с введением временной переменной, рассмотренный ранее. 

public class ArrayInverter {
    public static void invert(int[] array) {
        for (int i = 0; i < array.length / 2; i++) {
            int tmp = array[i];
            array[i] = array[array.length - i - 1];
            array[array.length - i - 1] =  tmp;
        }
    }
}

Обратите внимание что в классе ArrayInverter нет метода main() - будем вызывать метод invert() из другого класса. Для вызова метода, находящегося в другом классе, пишем имя класса - ArrayInverter.invert(array1):

import java.util.Arrays;

public class ArrayInverterTest1 {
    public static void main(String[] args) {
        int[] array1 = new int[]{};
        System.out.print(Arrays.toString(array1) + " => ");
        ArrayInverter.invert(array1);
        System.out.println(Arrays.toString(array1));

        array1 = new int[]{0};
        System.out.print(Arrays.toString(array1) + " => ");
        ArrayInverter.invert(array1);
        System.out.println(Arrays.toString(array1));

        array1 = new int[]{0, 1};
        System.out.print(Arrays.toString(array1) + " => ");
        ArrayInverter.invert(array1);
        System.out.println(Arrays.toString(array1));

        array1 = new int[]{0, 1, 2};
        System.out.print(Arrays.toString(array1) + " => ");
        ArrayInverter.invert(array1);
        System.out.println(Arrays.toString(array1));

        array1 = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        System.out.print(Arrays.toString(array1) + " => ");
        ArrayInverter.invert(array1);
        System.out.println(Arrays.toString(array1));
    }
}

Если мы внимательно посмотрим на код у классе ArrayInverterTest1, то увидим, что один блок кода повторяется пять раз. Дублирование кода - это плохая практика, поэтому вынесем повторяющийся код в отдельный метод, который будет вызываться пять раз с разными значениями: 

import java.util.Arrays;

public class ArrayInverterTest2 {
    public static void main(String[] args) {
        testInvert(new int[]{});
        testInvert(new int[]{0});
        testInvert(new int[]{0, 1});
        testInvert(new int[]{0, 1, 2, 3, 4});
    }

    private static void testInvert(int[] array) {
        System.out.print(Arrays.toString(array) + " => ");
        ArrayInverter.invert(array);
        System.out.println(Arrays.toString(array));
    }
}

4. Сортировка

Существует достаточно много алгоритмов сортировки и их модификаций. Виды сортировки:

  1. Пузырьком + модификации
  2. Выбором
  3. Вставками
  4. Поразрядная
  5. Быстрая
  6. Пирамидальная
  7. Слиянием
  8. Шелла
  9. Топологическая
  10. Быстрая с составными ключами

Мы рассмотрим только некоторые их них.

4.1. Сортировка пузырьком

Начнем с любимой всеми учебной сортировки пузырьком.  

Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.

Расположим массив сверху вниз, от нулевого элемента - к последнему.

Сортировка пузырьком

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

Сортировка пузырьком

Пример 5. Сортировка пузырьком

Рассмотрим программу сортировки пузырьком. Внешний цикл for отвечает за номер прохода, а внутренний - за перебор элементов в одном проходе. Обмен значений производится с помощью временной переменной tmp. Во внутреннем цикле перебираем значения начиная с последнего (array.length - 1) и в каждом следующем проходе уменьшаем количество просмотренных элементов (j > i).

public class BubbleSorter {
    public static void sort(int[] array) {
        // i - номер прохода
        for (int i = 0; i < array.length - 1; i++) {
            // внутренний цикл прохода
            for (int j = array.length - 1; j > i; j--) {
                if (array[j - 1] > array[j]) {
                    int tmp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }
}

Будем вызывать метод BubbleSorter.sort() из класса BubbleSorterTest, приведенного ниже. Отсортируем каждую строку многомерного массива data:

import java.util.Arrays;

public class BubbleSorterTest {
    public static void main(String[] args) {
        int[][] data = {
                {},
                {1},
                {0, 3, 2, 1},
                {4, 3, 2, 1, 0},
                {6, 8, 3, 123, 5, 4, 1, 2, 0, 9, 7},
        };
        for (int[] arr : data) {
            System.out.print(Arrays.toString(arr) + " => ");
            BubbleSorter.sort(arr);
            System.out.println(Arrays.toString(arr));
        }
    }
}

4.2. Сортировка выбором

Еще один вариант сортировки - это сортировка выбором. Идея метода: ищем минимальный элемент в массиве и меняем его местами с элементом, находящимся в позиции ноль. Далее ищем следующий по величине элемент и меняем его с элементом с индексом 1 и т.д:

Сортировка выбором

Пример 6. Сортировка выбором

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

public class SelectionSorter {
    public static void sort(int[] array) {
        for (int i = 0; i < array.length; i++) {    // i - номер текущего шага
            int pos = i;
            int min = array[i];
            // цикл выбора наименьшего элемента
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < min) {
                    pos = j;    // pos - индекс наименьшего элемента
                    min = array[j];
                }
            }
            array[pos] = array[i];
            array[i] = min;    // меняем местами наименьший с array[i]
        }
    }
}
import java.util.Arrays;

public class SelectionSorterTest {
    public static void main(String[] args) {
        int[][] data = {
                {},
                {1},
                {0, 3, 2, 1},
                {4, 3, 2, 1, 0},
                {6, 8, 3, 123, 5, 4, 1, 2, 0, 9, 7},
        };
        for (int[] arr : data) {
            System.out.print(Arrays.toString(arr) + " => ");
            SelectionSorter.sort(arr);
            System.out.println(Arrays.toString(arr));
        }
    }
}

 

Литература: Sorting Algorithms AnimationsПузырьковая сортировка и все-все-всеАлгоритмы сортировки




0 Comments
Leave your comment: