Отсортируйте данный массив по спирали, начиная с центра

Учитывая массив arr[] размера N , задача состоит в том, чтобы отсортировать массив в порядке убывания, начиная с середины массива, имеющего следующий по величине элемент справа от среднего элемента и следующий по величине слева от среднего элемента и так далее.

Примеры:

Input: arr[] = {4, 9, 3, 5, 7}
Output: 3 5 9 7 4
Explanation:
The largest element in the array is 9 is kept in the middle of the array at index = 2.
The next largest element is 7 is placed to the right of the middle element at index = 3.
The 3rd largest element is 5 is placed to the left of the middle element at index = 1.
The 4th largest element is 4 is placed to the right of the element is 7 at index = 4.
The smallest element is 3 is placed to left of the element is 5 at index = 0.

Input: arr[] = {4, 5, 3, 7, 6, 9, 7}
Output: 3 5 7 9 7 6 4
Explanation:
The largest element in the array is 9 is kept in the middle of the array at index = 3.
The next largest element is 7 is placed to the right of the middle element at index = 3.
The 3rd largest element is 7 is placed to the left of the middle element at index = 2.
The 4th largest element is 6 is placed to the right of the element 7 at index = 5.
The 5th largest element is 5 is placed to the left of the element 7 at index = 1.
The 6th largest element is 4 is placed at the right of the element 6 at index = 6.
The smallest element is 3 is placed to the left of the element 5 at index = 0.

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

• Инициализируйте переменные, скажем, left = 0 , right = N – 1 и i = 1 .
• Начните с левой позиции, т.е. слева = 0 , затем выполните пузырьковую сортировку в оставшейся части массива, найдя наименьший элемент и поместив его в крайнее левое положение, пока i == right .
• Увеличьте значение left на 1 , так как его элемент уже размещен и его не нужно изменять.
• Начните с правой позиции и снова выполните пузырьковую сортировку в обратном направлении, найдя наименьший элемент и поместив его в позицию справа до тех пор, пока i == left .
• Уменьшите значение right на 1 , так как его элемент уже размещен и его не нужно изменять.
• Если N четно, наименьший элемент должен находиться в крайнем правом углу массива, но в нашем подходе наименьший элемент помещается в крайний левый край. Итак, для получения нужного шаблона переверните первую половину массива.
• Распечатайте измененный отсортированный массив.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ² )
Вспомогательное пространство: O(1)