Сортировать массив в линейном таймере и на месте - PullRequest
Новая
       40

Сортировать массив в линейном таймере и на месте

3 голосов
/ 05 января 2012

происхождение вопроса

Учитывая несортированный массив размера n, содержащий объекты с идентификаторами 0… n-1, отсортируйте массив по месту и по линейному времени. Предположим, что объекты содержат большие элементы, такие как двоичные данные, поэтому создание новых копий объектов является непомерно дорогим. 

void linearSort(int* input, const int n) {
    for (int i = 0; i < n; i++) {
        while (input[i] != i) {
            // swap
            int swapPoint = input[i];
            input[i] = input[swapPoint];
            input[swapPoint] = swapPoint;
        }
    }
}

Это линейно? Работает ли этот вид с любым массивом целых? Если так, зачем нам нужна быстрая сортировка?

Ответы [ 2 ]

2 голосов
/ 05 января 2012

Несмотря на цикл while внутри for, этот тип является линейным O(n).Если цикл while происходит несколько раз для данного i, то для значений i, которые соответствуют swapPoint, цикл while не будет выполняться вообще.

Эта реализация будет работать только для массивов целых чиселтам, где нет дубликатов и значения последовательны от 0 до n-1, поэтому Quicksort все еще имеет значение O(n log n), потому что он работает с непоследовательными значениями.

Это можно легко проверить, выполнивнаихудший случай: 

input = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};

с последующим использованием следующего кода: 

int whileCount = 0;
for (int i = 0; i < n; i++)
{
    while (input[i] != i)
    {
        whileCount++;
        // swap
        int swapPoint = input[i];
        input[i] = input[swapPoint];
        input[swapPoint] = swapPoint;
    }
    Console.WriteLine("for: {0}, while: {1}", i, whileCount);
}

Вывод будет следующим: 

for: 0, while: 9
for: 1, while: 9
for: 2, while: 9
for: 3, while: 9
for: 4, while: 9
for: 5, while: 9
for: 6, while: 9
for: 7, while: 9
for: 8, while: 9
for: 9, while: 9

, поэтому вы видите даже вв худшем случае, когда вы выполняете цикл while n-1 раз в первой итерации цикла for, вы все равно получаете только n-1 итераций цикла while для всего процесса.

Дополнительные примеры со случайными данными: 

{7, 1, 2, 4, 3, 5, 0, 6, 8, 9} => 2 on i=0, 1 on i=3 and nothing more. (total 3 while loop runs)
{7, 8, 2, 1, 0, 3, 4, 5, 6, 9} => 7 on i=0 and nothing more (total 7 while loop runs)
{9, 8, 7, 4, 3, 1, 0, 2, 5, 6} => 2 on i=0, 2 on i=1, 1 on i=2, 1 on i=3 (total 6 while loop runs)
0 голосов
/ 05 января 2012

Каждый вы ставите input[i] в положение swapPoint, которое именно туда, куда нужно идти.Таким образом, в следующих шагах эти элементы уже находятся в нужном месте, и общее время обмена не будет превышать размер n.

...