Урок 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("Average is " + result / nums.length);
    }
}

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

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

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

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

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

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

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. Обмен значениями

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);
    }
}

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

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

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;
        }
    }
}
import java.util.Arrays;

import static arrays.ArrayInverter.invert;

public class ArrayInverterTest1 {
    public static void main(String[] args) {
        int[] array1;

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

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

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

        array1 = new int[]{0, 1, 2};
        System.out.print(Arrays.toString(array1) + " => ");
        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) + " => ");
        invert(array1);
        System.out.println(Arrays.toString(array1));
    }
}
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. Сортировка пузырьком

public class BubbleSorter {
    public static void sort(int[] array) {
        // i - номер прохода
        for (int i = 0; i < array.length; 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;
                }
            }
        }
    }
}
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. Сортировка выбором

Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке. На i-м шаге выбираем наименьший из элементов a[i] ... a[n] и меняем его местами с a[i].

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

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

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: