Программа Javascript для сортировки массива в форме волны

Опубликовано: 2 Сентября, 2022

Учитывая несортированный массив целых чисел, отсортируйте массив в волнообразный массив. Массив 'arr[0..n-1]' сортируется в форме волны, если arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= … ..

Примеры:

 Input:  arr[] = {10, 5, 6, 3, 2, 20, 100, 80}
 Output: arr[] = {10, 5, 6, 2, 20, 3, 100, 80} OR
                 {20, 5, 10, 2, 80, 6, 100, 3} OR
                 any other array that is in wave form

 Input:  arr[] = {20, 10, 8, 6, 4, 2}
 Output: arr[] = {20, 8, 10, 4, 6, 2} OR
                 {10, 8, 20, 2, 6, 4} OR
                 any other array that is in wave form

 Input:  arr[] = {2, 4, 6, 8, 10, 20}
 Output: arr[] = {4, 2, 8, 6, 20, 10} OR
                 any other array that is in wave form

 Input:  arr[] = {3, 6, 5, 10, 7, 20}
 Output: arr[] = {6, 3, 10, 5, 20, 7} OR
                 any other array that is in wave form

Простое решение — использовать сортировку. Сначала отсортируйте входной массив, затем поменяйте местами все соседние элементы.
Например, пусть входной массив будет {3, 6, 5, 10, 7, 20}. После сортировки получаем {3, 5, 6, 7, 10, 20}. После замены соседних элементов мы получаем {5, 3, 7, 6, 20, 10}.

Ниже приведены реализации этого простого подхода.

Выход:

2 1 10 5 49 23 90

Временная сложность приведенного выше решения составляет O (nLogn), если используется алгоритм сортировки O (nLogn), такой как сортировка слиянием, сортировка кучей и т. д.
Это можно сделать за время O(n), выполнив один обход заданного массива. Идея основана на том факте, что если мы убедимся, что все четные элементы (с индексами 0, 2, 4, ..) больше, чем соседние с ними нечетные элементы, нам не нужно беспокоиться о нечетных элементах. Ниже приведены простые шаги.
1) Пройдите все четные элементы входного массива и выполните следующие действия.
….a) Если текущий элемент меньше предыдущего нечетного элемента, поменять местами предыдущий и текущий.
….b) Если текущий элемент меньше следующего нечетного элемента, поменять местами следующий и текущий.

Ниже приведены реализации вышеуказанного простого алгоритма.

Выход:

90 10 49 1 5 2 23

Пожалуйста, обратитесь к полной статье о сортировке массива в форме волны для получения более подробной информации!

JavaScript

Программа Javascript для сортировки массива в форме волны

РЕКОМЕНДУЕМЫЕ СТАТЬИ