Оптимизация кода

[Saruman!]

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int A[n];
    for(int i=0;i<n;i++)
        cin >> A[i];
    int j=0,i=0;
    for(i;i<n;i++)
    {
        for(j=1;j<n;j++)
        {
            if(A[j]%2 == 0 && A[j-1]%2 != 0)
                swap(A[j-1],A[j]);
        }
    }
    for(int i=0;i<n;i++)
        cout << A[i] << " ";
}

Не использовать функции и методы. Упростить сложность программы.
Данный алгоритм имеет сложность n^2.
Прошу помочь пожалуйста.

Программа делит массив сохраняя порядок чисел на чётные и нечётные числа.
В левой стороне все чётные числа, а в правой все нечётные.

Пример : 5 3 2 4 7 8

Вывод : 2 4 8 5 3 7

[ura_111]

Вроде сложность: 3*n = n

0.jpg

[Saruman!]

Извиняюсь, забыл дополнить условие. Создавать дополнительные массивы нельзя.

[Sibedir]

https://ru.wikipedia.org/wiki/Устойчивая_сортировка
раздел: Алгоритмы сортировки слиянием без дополнительной памяти

[ura_111]

Попробуй так:

0.jpg

0_0.jpg

0_1.jpg

[Sibedir]

Кстати, Saruman!, там вроде ошибка. У тебя, как-бы пузырьковая сортировка. Обрати внимание на диапазоны циклов

...
    int j=0,i=0;
    for(i;i<n;i++)
    {
        for(j=1;j<n;j++)
...

https://ru.wikipedia.org/wiki/%D0%A1...86.D0.B8.D1.8F

Я делаю i от 1 до N-1, а j от 0 до N-i-1. И сравниваю A[j] и A[j+1].