Реализация сортировки вставок

Question

Вот мой код.

#include<stdio.h>
void insert(int member,int arr[],int size)
{
    int i,j;
    for(i=0;i<size;i++)
    {
        if(member<arr[i])
        {

            for( j=0;j<size-i;j++)
            {
                arr[size]=arr[size-1];
        }
         arr[i]=member;
         break;
         }
    }    
}
void insertsort(int arr[],int size)
{
    int newsize=1,member;
    for(newsize=1;newsize<size;newsize++)
    {
    member=arr[newsize];
    insert(member,arr,newsize);
    }
}
void main()
{
    int arr[100];
    int size,i;
    printf("enter the size");
    scanf("%d",&size);
    printf("enter numbers");
    for( i=0;i<size;i++)
    {
        scanf("%d",&arr[i]);
    }
    insertsort(arr,size);
    for(i=0;i<size;i++)
    printf("\n %d",arr[i]);
}

Не знаю, в чем проблема, но при вводе

Количество элементов: 5;

ВХОДНЫЕ НОМЕРА 45 23 87 345 12

ВЫХОД 12 45 87 345 345.

Может кто-нибудь сказать мне, в чем проблема?

Answer 1

В вашей функции вставки измените arr[size]=arr[size-1]; на arr[size-j]=arr[size-j-1];.

Когда вы делаете вставку, я думаю, что вы хотели сдвинуть все числа после шага вставки на 1 шаг вправо, но вместо этого вы сместили только самое правое.

void insert(int member,int arr[],int size)
{
    int i,j;
    for(i=0;i<size;i++)
    {
        if(member<arr[i])
        {
            for( j=0;j<size-i;j++)
            {
                arr[size-j]=arr[size-j-1];
            }
            arr[i]=member;
            break;
         }
    }     
}

Answer 2

A - массив с несортированными элементами. Идея очень похожа на то, как вы сортируете карты в руке в типичной карточной игре. Вы берете первую карту. Затем вы выбираете вторую карту и т. Д. И сравниваете ее в обратном направлении, пока не найдете карту, стоимость которой больше текущей карты. Затем вы вставляете текущую карту в это место, фактически сдвигая все карты вправо при движении назад. После этого цикла все элементы в вашей руке сортируются. У меня есть более подробное описание на http://www.worldkosh.com/2016/12/22/insertion-sort/

Статья вдохновлена ​​Cormen, Thomas H .; Leiserson, Charles E .; Ривест, Рональд Л .; Stein, Clifford (2001) [1990]. Введение в алгоритмы (2-е изд.).

псевдокод Предполагая, что начальный индекс равен 0

Insertion_sort(array A) {
    for(int i = 1;i < n; i++) {
        key = A[i];
        for(int j = i-1; j>= 0 and A[j]>key; j--) {
            A[j +1] = A[j];
        }
        A[j+1] = key;       
    }  
}

Answer 3

Вот сортировка вставки в C #. Вы можете легко конвертировать его в C или C ++

class Program
{
    static void Main(string[] args)
    {
        int[] set = new[] { 5, 3, 2, 9, 6, 1, 7, 2 };
        int[] result = InsertionSort(set);
    }

    static int[]  InsertionSort(int[] list) {
        if (list.Length < 2) {
            return list;
        }
        for (int i = 0; i < list.Length - 1; i++) {
            for (int j = i + 1; j > 0 && list[j - 1] > list[j]; j--) {
                int temp = list[j - 1];
                list[j - 1] = list[j];
                list[j] = temp;
            }  
        }
        return list;
    }
}

Answer 4

Вот код для вставки сортировки:

int InsertionSort()
{
    int max;
    int *numarray = 0;
int i,j,k,temp;

printf("\nProgram for Ascending order of Numeric Values using INSERTION SORT");
    printf("\n\nEnter the total number of elements: ");
    scanf("%d", &max);   

    numarray = (int*) malloc(sizeof(int) * max);

    for(i = 0; i < max; i++)
    {
        printf("\nEnter [%d] element: ", i + 1);
        scanf("%d", &numarray[i]);
    }

    printf("Before Sorting   : ");
    for(k = 0; k < max; k++)
        printf("%d ", numarray[k])
    printf("\n");

    for(i = 1; i < max; i++)
    {
        j = i;
        while(j > 0)
        {
            if(numarray[j-1] > numarray[j])
            {
                temp = numarray[j - 1];
                numarray[j - 1] = numarray[j];
                numarray[j] = temp;
                j--;
            }
            else
                break;
        }
        printf("After iteration %d ": ", i);
        for(k = 0; k < max; k++)
            printf("%d ", numarray[k] );
        printf("/*** %d numbers from the begining of the array are input and they are sorted ***/\n", i + 1);
    }

    printf("\n\nThe numbers in ascending orders are given below:\n\n");
    for(i = 0; i < max; i++)
    {
        printf("Sorted [%d] element: %d\n",i + 1, numarray[i]);
    }

    free(numarray);
    return 0;
}

Вывод будет

Программа для возрастания числовых значений с использованием INSERTION SORT

Введите общее количествоэлементы: 8

Введите [1] элемент: 80

Введите [2] элемент: 60

Введите [3] элемент: 40

Введите [4] элемент: 20

Введите [5] элемент: 10

Введите [6] элемент: 30

Введите [7] элемент: 50

Введите элемент [8]: 70

Числа в порядке возрастания приведены ниже:

Сортированный [1] элемент: 10

Сортированный [2] элемент: 20

Сортированный элемент [3]: 30

Сортированный элемент [4]: ​​40

Сортированный элемент [5]: 50

Сортированный элемент [6]: 60

Сортированный [7] элемент: 70

Сортированный [8] элемент: 80

Answer 5

 for(i=1; i<N; i++)
    {
        Temp = A[i];
        j = i-1;
        while(Temp<A[j] && j>=0)
        {
            A[j+1] = A[j];
            j = j-1;
        }
        A[j+1] = Temp;
    }