Переставить по месту четные элементы в начало в одномерном массиве

#массивы #алгоритм #любой_язык

Не могу понять алгоритм перестановки элементов в этой задаче:


  Дан массив. Без использования дополнительного массива переставить элементы так,
чтобы вначале шли все элементы под четными исходными индексами, затем - нечетными.
  
  Пример:
  Исходный массив 3 5 1 6 0 4 6
  Выход 3 1 0 6 5 6 4*


Приведите пожалуйста пример на каком-нибудь языке. Или словесное описание алгоритма.
    

Ответы

Ответ 1

Очевидный "лобовой" алгоритм - проходим по элементам с четными индексами s и при
помощи последовательного применения обмена элемента массива с соседом слева "загоняем"
этот элемент в его правильное положение d.

Например, для 3 5 1 6 0 4 6:

s = 0, d = 0: элемент [0] (3) и так на месте
s = 2, d = 1: элемент [2] (1) должен попасть на место [1]. Обмениваем [1]-[2]
3 1 5 6 0 4 6
s = 4, d = 2: элемент [4] (0) должен попасть на место [2]. Обмениваем [4]-[3], [3]-[2]
3 1 0 5 6 4 6
s = 6, d = 3: элемент [6] (6) должен попасть на место [3]. Обмениваем [6]-[5], [5]-[4],
[4]-[3]
3 1 0 6 5 6 4

Каждая последовательноcть обменов - это на самом деле циклический сдвиг вправо для
подмассива [d, s], который можно реализовать несколько более эффективно, чем вышеописанная
последовательность обменов.

В С++, например, можно воспользоваться готовой функцией std::rotate, хотя сдвиг на
1 элемент в любом случае реализуется тривиально

#include 
#include 
#include 

int main()
{
  int a[] = { 3, 5, 1, 6, 0, 4, 6 };
  size_t N = sizeof a / sizeof *a;

  std::copy_n(std::begin(a), N, std::ostream_iterator(std::cout, " "));
  std::cout << std::endl;

  for (std::size_t s = 0, d = 0; s < N; s += 2, ++d)
    std::rotate(a + d, a + s, a + s + 1);

  std::copy_n(std::begin(a), N, std::ostream_iterator(std::cout, " "));
  std::cout << std::endl;
}


Ответ 2

для разнообразия и лучшего понимания, приведу реализацию лобового алгоритма из ответа
@Ant  но без использования std::rotate

#include 
#include 
#include 
#include 

void f(std::vector& a)
{  
    std::vector::size_type N = a.size();
    for (int i = 0, j = 0, k = 0; i < N; i += 2, ++k)
    {
        for (int j = i; j > k; --j)
        {
            std::swap(a[j], a[j-1]);
        }
    }
}

int main()
{
    std::vector a = {3, 5, 1, 6, 0, 4, 6};     
    f(a);    
    std::copy_n(std::begin(a), a.size(), std::ostream_iterator(std::cout, " "));
    std::cout << std::endl;

    std::vector b = { 7, 8, 3, 0, 1, 4, 5, 11 }; 
    f(b);    
    std::copy_n(std::begin(b), b.size(), std::ostream_iterator(std::cout, " "));
    std::cout << std::endl;
}