Перестановка чисел в массиве

Question

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    long long arr1[n];
    for (int i = 0; i < n; i++) {
        cin >> arr1[i];
    }
    for (int i = 0; i < n; i++) {
        for (int k = i; k < n; k++) {
            if (arr1[k] % 2 == 0) {
                long long t = arr1[k];
                arr1[k] = arr1[i];
                arr1[i] = t;
            }
        }
        cout << arr1[i] << " ";
    }
}

Нужно переставить чётные и нечётные числа в массиве так, чтобы чётные были в начале, а нечётные только после них. Последовательность должна сохраняться

Числа переставляются но последовательность не сохраняется, прошу о помощи

Answer 1

Это же С++, так что в одну строку -

stable_sort(arr1,arr1+n,[](auto a, auto b) { return abs(a)%2 < abs(b)%2; });

Если я правильно понял ваше "последовательность должна сохраняться"...

Answer 2

#include <iostream>

#include <stdio.h>
#include <stdlib.h>


using namespace std;

void print_arr (long long a[], size_t n)
{
  for (size_t i = 0, j = 0; i < n; i++)
    cout << a[i] << ' ';
  cout << '\n';
}

int main() {
  int n;
  cin >> n;
  long long arr1[n];
  for (int i = 0; i < n; i++) {
    arr1[i] = random() % 100;
    if (random() % 100 > 49)
      arr1[i] = -arr1[i];
  }

  print_arr(arr1, n);

  long long *t = (__typeof__(t))malloc(n * sizeof(t[0]));
  size_t j = 0, k = 0;
  for (size_t i = 0; i < n; i++) 
    if (arr1[i] & 1LL) // odd number
      t[k++] = arr1[i];
    else
      arr1[j++] = arr1[i];

  print_arr(arr1, j);
  print_arr(t, k);

  for (size_t i  = 0; j < n; j++)
    arr1[j] = t[i++];
  free(t);
  
  print_arr(arr1, n);

  return puts("End") == EOF;
}

Answer 3

stable_partition решает задачу за линейное время если есть дополнительная память и за NlogN если её нет.

// g++ -std=c++11 -pedantic -Wall -Wextra -Werror stable-partition.cpp

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    std::vector<long long> a;

    std::copy_n(
        std::istream_iterator<long long>(std::cin),
        n,
        std::back_inserter(a)
    );

    std::stable_partition(
        a.begin(),
        a.end(),
        [](long long v) { return v % 2 == 0; }
    );

    std::copy(
        a.begin(),
        a.end(),
        std::ostream_iterator<long long>(std::cout, " ")
    );
    std::cout << '\n';
}

$ g++ -std=c++11 -pedantic -Wall -Wextra -Werror stable-partition.cpp
$ echo 11 1 2 3 4 5 6 7 8 9 -1 -2 | ./a.out 
2 4 6 8 -2 1 3 5 7 9 -1

Пара замечаний

Стандартный C++ не содержит variable length arrays. Это про строку long long arr1[n];, где n не константа. GCC поддерживает их как расширение, но vector тут уместнее.

Раз уж у нас тут такой C++ образовался, то читать/писать массивы тоже логичнее без циклов.

БЛОГ НА HUSL

Перестановка чисел в массиве

Ответы (3 шт):