«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).

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

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

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

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