Сортировка по O (n) без какой-либо временной переменной

Question

Мне нужно спроектировать алгоритм, который будет сортировать массив, который содержит только числа -1,0,1, без использования какой-либо временной переменной или массива и с помощью только подкачки. Я пришел к следующему методу, я не уверен если это O (n).

#include <stdio.h>
#define MAXSIZE 10

int main()
{
    int array[MAXSIZE];
    int i, j, num = 8, temp;

    int list[] = {-1,0,-1,0,1,1,0,1};

    int size = sizeof(list)/sizeof(list[0]);
    for (int i = 1; i < size; i++) {

        if (list[i] < list[i - 1]) {
            list[i] = list[i] + list[i - 1];
            list[i - 1] = list[i] - list[i - 1];
            list[i] = list[i] - list[i - 1];
            i = 0;
        }
    }

    printf("Sorted array is...\n");
    for (int i = 0; i < size; i++)
    {
        printf("%d\n", list[i]);
    }
}

Answer 1

Алгоритм определенно не O (n).
Вы устанавливаете i в 0, когда делаете своп.В худшем случае это O (n ^ 2).

Answer 2

Причина, по которой @RSahu правильно сформулировал ваш алгоритм, вы сбрасываете счетчик на 0, что означает, что вы можете делать до 1+2+...+n итераций.

Вот небольшой пример, показывающий линейное время для обработки массива:

#include <iostream>
#include <array>

using namespace std;

int main() {
    array<int,10> A{-1, 0, -1, 0, 1, 1, 0, 1, 0, -1};

    int i=0,j=0, k=9;
    while(j!=k) {
        if(A[j] == 0) {
            ++j;
        }
        else if(A[j] == -1) {
            swap(A[i], A[j]);
            ++i; ++j;
        }
        else {
            swap(A[j], A[k]);
            --k;
        }
    }

    for(auto ai : A)
        cout << ai << " ";
    cout << endl;
}

Вы можете увидеть его вживую там .

Как это работает? Мы поддерживаем три счетчика i, j и k с инвариантами, которые:

• все предметы в ассортименте: [0, i) -1
• все товары в ассортименте: [i, j) 0
• все товары в ассортименте: (k, n-1) +1

Где [ означает включающую границу, а ) или ( означает эксклюзивную границу.

Первоначально

i=j=0 и 'k = n-1`. Инварианты соблюдаются.

Первый случай

if(A[j] == 0) {
    ++j;
}

Значение A[j] равно 0, поэтому мы можем увеличивать j, а инварианты по-прежнему сохраняются.

Второй случай

else if(A[j] == -1) {
    swap(A[i], A[j]);
    ++i; ++j;
}

Поскольку i является эксклюзивной границей, мы добавляем -1 к предыдущему диапазону -1, и необходимо увеличение i. Если диапазон [i, j) не был пустым, 0 был скопирован в позицию j, и мы должны увеличить j. Если диапазон был пустым, то у нас было i==j, и при увеличении i мы также должны увеличивать j, чтобы сохранить инвариант. Мы можем заключить, что инварианты остаются в силе после этого шага.

Третий случай

else {
    swap(A[j], A[k]);
    --k;
}

A[j] равно 0 мы можем поменять его на значение A[k] и уменьшить k, и инварианты сохранятся.

Окончание и корректность

Последний пункт - завершение программы. Каждый шаг либо: - приращение j - уменьшение k Таким образом, расстояние между j и k будет уменьшаться на 1 каждый шаг.

Расстояние между j и k изначально равно n-1 и уменьшается на один шаг. Таким образом, будет не более 1093 шагов. Каждый шаг делает один обмен. Будет не более n-1 свопов.

В конце программы сохранятся инварианты:

• с 0 до i исключено, все -1
• с i до j==k исключено, все 0
• с j==k до n-1 исключено, все +1