Волновая сортировка в O (N) времени сложности

Question

Волновая сортировка массив по временной сложности O (n)

Волновая сортировка в массиве так, что он образует волну. например: 3, 1, 4, 2, 8, 7 это будет отсортированный массив после применения сортировки волны

Я ожидаю вывод 3, 1, 4, 2, 8, 7, если задано значение 1, 3, 4, 2, 7, 8. Результаты могут отличаться в зависимости от реализации. Основная цель - создать гребень и впадину в массиве, как волна, и сделать это за O (n).

Answer 1

Спасибо за попытку помочь. Но я нашел решение, которое работает в O (n) .

def waveSort(a):
    n = len(a)
    for i in range(0, n-1, 2):

        if i > 0 and a[i-1] > a[i]:
            a[i], a[i-1] = a[i-1], a[i]

        if i <= n-2 and a[i+1] > a[i]:
            a[i], a[i+1] = a[i+1], a[i]
    return arr

Вот ссылка на полный файл на github

github.com/ WaveSort

Answer 2

Примите во внимание, что вы можете получить отсортированный по волнам массив из линейно отсортированного массива, просто пройдя по массиву один раз и поменяв местами каждую пару встреченных чисел. Используя ваш пример ввода:

1, 2, 3, 4, 7, 8

Мы можем пройтись по массиву и поменять местами каждую пару чисел, дав:

2, 1, 4, 3, 7, 8

Штраф за сортировку массива с использованием чего-то вроде сортировки слиянием,или сопоставимый метод «разделяй и властвуй» был бы O(N*lgN), где N - размер массива. Кроме того, нам понадобится одна операция O(N) для наложения волновой сортировки. Итак, общий порядок может быть:

O(N*lgN + N) = O(N*lgN)