Руководство по работе алгоритма сортировки на месте с реализацией Java

1. Введение

В этом руководстве мы объясним, как работает алгоритм сортировки на месте.

2. Алгоритмы на месте

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

Однако на самом деле алгоритм может потребовать небольшого и непостоянного дополнительного пространства для вспомогательных переменных. Сложность этого пространства в большинстве случаев O(log n) , хотя иногда допускается что-то меньшее, чем линейное.

3. Псевдокод

Давайте теперь посмотрим на некоторый псевдокод и сравним алгоритм на месте с алгоритмом на месте.

Предположим, что мы хотим перевернуть массив из n чисел.

3.1. Алгоритм на месте

Если мы подумаем о проблеме, мы увидим, что у нас есть входной массив и инвертированный массив в качестве вывода. В конце концов, нам на самом деле не нужен исходный массив, а только перевернутый.

Тогда почему бы нам не перезаписать ввод вместо того, чтобы переместить его значения в совершенно новый массив, поскольку это может выглядеть как наиболее очевидный метод? Для этого нам понадобится только одна дополнительная переменная для временного хранения значений, с которыми мы сейчас работаем:

reversInPlace(array A[n])
    for i from 0 to n/2
    temp = A[i]
    A[i] = A[n - 1 - i]
    A[n - 1 - i] = temp

Стоит отметить, что независимо от того, насколько велик массив, в этом случае дополнительное пространство, которое нам нужно, всегда будет O (1) .

На иллюстрации видно, что нам нужно меньше шагов, чем в предыдущем случае:

3.2. Неуместный алгоритм

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

reverseOutOfPlace(array A[n])
    create new array B[n]
    for i from 0 to n - 1
        B[i] = A[i]
    delete A
    return B

Хотя это будет делать то, что мы хотели, это недостаточно эффективно. Нам требуется O(n) дополнительного пространства, так как у нас есть два массива для работы с . Кроме того, создание и удаление нового массива обычно является медленной операцией.

Давайте посмотрим на иллюстрацию процесса:

4. Реализация Java

Давайте теперь посмотрим, как мы можем реализовать на Java то, что узнали в предыдущем разделе.

Во-первых, мы реализуем алгоритм на месте:

public static int[] reverseInPlace(int A[]) {
    int n = A.length;
    for (int i = 0; i < n / 2; i++) {
        int temp = A[i];
        A[i] = A[n - 1 - i];
        A[n - 1 - i] = temp;
    }
    return A;
}

Мы можем легко проверить, что это работает так, как ожидалось:

@Test
public void givenArray_whenInPlaceSort_thenReversed() {
    int[] input = {1, 2, 3, 4, 5, 6, 7};
    int[] expected = {7, 6, 5, 4, 3, 2, 1};
    assertArrayEquals("the two arrays are not equal", expected,
      InOutSort.reverseInPlace(input));
}

Во-вторых, давайте проверим реализацию неуместного алгоритма:

public static int[] reverseOutOfPlace(int A[]) {
    int n = A.length;
    int[] B = new int[n];
    for (int i = 0; i < n; i++) {
        B[n - i - 1] = A[i];
    }
    return B;
}

Тест довольно простой:

@Test
public void givenArray_whenOutOfPlaceSort_thenReversed() {
    int[] input = {1, 2, 3, 4, 5, 6, 7};
    int[] expected = {7, 6, 5, 4, 3, 2, 1};
    assertArrayEquals("the two arrays are not equal", expected,
      InOutSort.reverseOutOfPlace(input));
}

5. Примеры

Существует множество алгоритмов сортировки, использующих подход на месте. Некоторыми из них являются сортировка вставками , пузырьковая сортировка , сортировка кучи , быстрая сортировка и сортировка оболочки , и вы можете узнать о них больше и ознакомиться с их реализациями Java.

Также нужно упомянуть гребенчатую сортировку и пирамидальную сортировку. Все они имеют пространственную сложность O(log n) .

Также было бы полезно узнать больше о Theory of Big-O Notation , а также ознакомиться с некоторыми практическими примерами Java о сложности алгоритма .

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

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

Как обычно, весь код можно найти на GitHub .