Двусторонняя вставка

Question

Я пытаюсь сделать сортировку с 2 путями, которая соответствует следующим условиям:

• Первый элемент массива должен быть помещен как средний элемент.
• Как только непрерывная группа элементов находится в массиве, место для нового элемента создается путем смещения всех меньших элементов на один шаг влево или всех более крупных элементов на один шаг вправо, и каждый раз, когда новые элементы должны сравниваться и сортироваться ,

Но я не могу получить меньшие и большие элементы с обеих сторон. Ваши предложения будут высоко оценены

Я пытался использовать 2 массива. Предположим, что a и b - это 2 массива. Я поместил a[0] в b[mid], где mid - средний элемент массива b, и сравнил все элементы массива a с b[mid] и попытался увеличить и уменьшить.

Проблема, с которой я сталкиваюсь сейчас, заключается в том, что если я введу значение как 5 6 7 4 3, то результат будет 3 4 5 6 7. Но если я поменяю входное значение на 5 7 6 3 4, выходное значение будет 0 3 5 7 0. Это выходит из-под контроля. Я хочу это как отсортированный массив, который я не получаю. Может ли кто-нибудь помочь мне, как поставить логику для сортировки, а не выхода за пределы.

#include <stdio.h>

void main() {
    int a[20] = { 0 };
    int b[20] = { 0 };
    int mid1, mid2, n, i, low, high;

    printf("\nEnter Size of the array:\n");
    scanf("%d", &n);
    printf("Enter Array elements");

    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    printf("Elements before sorting:");
    for (i = 0; i < n; i++) {
        printf("%d\t", a[i]);
    }
    low = 0;
    high = n;
    mid1 = (low + high) / 2;
    mid2 = (low + high) / 2;
    b[mid1] = a[0];

    printf("\n The middle element is : %d", b[mid1]);
    for (i = 1; i < n; i++) {
        if (a[i] <= b[mid1]) {
            mid1 = mid1 - 1;
            b[mid1] = a[i];
        }
    }
    b[mid2] = a[0];
    for (i = 1; i < n; i++) {
        if (a[i] > b[mid2]) {
            mid2 = mid2 + 1;
            b[mid2] = a[i];
        }
    }
    printf("\nSecond array is :");
    for (i = 0; i < n; i++) {
        printf("%d\t", b[i]);
    }
}

Answer 1

Ваш алгоритм не работает:

• , если более половины элементов массива соответствуют какому-либо сравнению, что произойдет, если массив уже отсортирован в любом направлении, вы попытаетесь сохранить элементы за пределамиграницы b.
• , если у вас есть 2 элемента в b, любые другие элементы со значением между этими 2 элементами вообще не будут сохранены в b.

Сортировка вставкой обычно выполняется на месте, но вот модифицированная версия вашего кода, которая создает отсортированный массив в b с изменением сортировки вставки:

#include <stdio.h>

int main() {
    int a[20], b[20];
    int n, i, j;

    printf("Enter Size of the array: ");
    if (scanf("%d", &n) != || n < 1 || n > 20)
        return 1;

    printf("Enter Array elements: ");
    for (i = 0; i < n; i++) {
        if (scanf("%d", &a[i]) != 1)
            return 1;
    }
    printf("Elements before sorting:");
    for (i = 0; i < n; i++) {
        printf("\t%d", a[i]);
    }
    printf("\n");

    b[0] = a[0];
    for (i = 1; i < n; i++) {
        int t = a[i];
        for (j = i; j > 0 && dest[j - 1] > t; j--) {
            b[j] = b[j - 1];
        }
        b[j] = t;
    }

    printf("Sorted array is:");
    for (i = 0; i < n; i++) {
        printf("\t%d", b[i]);
    }
    printf("\n");
    return 0;
}