Отсортировать массив 2 * N элементов

Question

Необходимо отсортировать массив. Есть N, необходимо создать массив длинной в 2 * N элементов таким образом: a1, aN + 1, a2, aN + 2, a3, AN + 3, ... aN, a2 * N;

Входной массив:

0 1 2 3 4 5 6 7 8 9

Результат после сортировки:

0 5 1 6 2 7 3 8 4 9

Проблема задачи в том, что использовать дополнительные массивы запрещено. Можно использовать только переменные типа int tmp;

Пытался сделать такое, но удается лишь добиться такого успеха:

0 5 1 6 3 7 2 8 4 9

Задача вообще для перекомпоновки списков на СИ, но с массивами почти также. Не могу дойти до правильного алгоритма самостоятельно. Заранее спасибо!

UPD: Мой код для списка:

void CHANGE_STRUCT(int n) {

List *P = BegL;
List *Pk = BegL;
List *Pl = BegL;
int tmp;


for(int i = 1; i <= n; i++) {
    Pk = Pk -> link;
}

Pl = Pl -> link;
for(int i = 1; i < n; i++){
    P = P -> link;
    Pl = Pl -> link;
    tmp = Pk -> A;
    Pk -> A = P -> A;
    P -> A = tmp;
    tmp = Pl -> A;
    Pl -> A = Pk -> A;
    Pk -> A = tmp;
    Pk = Pk -> link;
    Pl = Pl -> link;
    P = P -> link;
}
printf("\nNew struct\n");
PRINT_STRUCT();}

Answer 1

В C односвязные списки можно редактировать передавая в функции адрес поля next в предыдущем узле. Так работает insert, который вставляет новый узел в начало списка. Так работает cut, который срезает голову списка и возвращает её. reorder использует два бегущих указателя - для первой и для второй половин списка. Узел указываемый вторым указателем вырезается и вставляется после узла указываемого первым.

Обратите внимание на нотацию: если функция не меняет список, она вызывается с указателем на голову списка: print(head). Если функция меняет список, она вызывается с указателем на указатель на голову. Голова может поменяться, это необходимо: insert(&head, ...). Про функцию reorder известно что она не меняет голову списка, её можно было бы вызывать как reorder(head, ...). Проявляем твёрдость, добавляем ещё один уровень косвенности: reorder(&head, ...). Нотация.

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

typedef struct node_t node_t;
struct node_t {
    int value;
    node_t *next;
};

void insert(node_t **head, node_t *node) {
    assert(node->next == NULL);
    node->next = *head;
    *head = node;
}

node_t *cut(node_t **head) {
    node_t *node = *head;
    *head = (*head)->next;
    node->next = NULL;
    return node;
}

void reorder(node_t **head, int n) {
    node_t **n1 = head;
    node_t **n2 = head;
    for (int i = 0; i < n; ++i) {
        n2 = &(*n2)->next;
    }
    for (int i = 0; i < n; ++i) {
        n1 = &(*n1)->next;
        insert(n1, cut(n2));
        n1 = &(*n1)->next;
    }
}

void print(node_t *head) {
    printf("[ ");
    for (; head != NULL; head = head->next) {
        printf("%d ", head->value);
    }
    puts("]");
}

int main() {
    node_t *head = NULL;
    for (int i = 9; i >= 0; --i) {
        node_t *node = malloc(sizeof(node_t));
        node->value = i;
        node->next = NULL;
        insert(&head, node);
    }
    print(head);
    reorder(&head, 5);
    print(head);
}

Answer 2

Функция move_to по индексу определяет где должен оказаться элемент с этого индекса. Если её последовательно применять в цикле i = move_to(i), окажется что индексы бегают по циклу. В этом цикле все числа надо переставить на следующую позицию (rearrange_loop). Чтобы не обрабатывать цикл несколько раз (что испортит результат) он обрабатывается только тогда когда встречен первый раз (fresh_loop).

Алгоритм квадратичный - это плата за неиспользование дополнительной линейной памяти. Есть ли способ решить без дополнительной памяти за линейное время для данной конкретной перестановки - не знаю.

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

int move_to(int n, int i) {
    if (i < n) {
        return 2 * i;
    } 
    return 2 * i + 1 - 2 * n;
}

bool fresh_loop(int n, int i) {
    for (int j = move_to(n, i); j != i; j = move_to(n, j)) {
        if (j < i) {
            return false;
        }
    }
    return true;
}

void rearrange_loop(int n, int i, int a[/* 2n */]) {
    int v = a[i];
    for (int j = move_to(n, i); j != i; j = move_to(n, j)) {
        int tmp = a[j];
        a[j] = v;
        v = tmp;
    }
    a[i] = v;
}

void rearrange(int n, int a[/* 2n */]) {
    for (int i = 0; i < 2 * n; ++i) {
        if (fresh_loop(n, i)) {
            rearrange_loop(n, i, a);
        }
    }
}

void print(int n, int a[/* 2n */]) {
    printf("[ ");
    for (int i = 0; i < 2 * n; ++i) {
        printf("%d ", a[i]);
    }
    puts("]");
}

int main() {
    int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    print(5, a);
    rearrange(5, a);
    print(5, a);
}

БЛОГ НА HUSL

Отсортировать массив 2 * N элементов

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