Программирование на C: как реализовать сортировку вставками?

Скажем, у меня есть список чисел:

89 12 18 4 6

и я хочу реализовать сортировку вставками и вывести на экран каждый шаг сортировки: 

Sort 1. 12 89 18 4 6
Sort 2. 4 12 89 18 6
Sort 3. 4 6 12 89 18
Sort 4. 4 6 12 18 89

вот код, который у меня есть до сих пор, я не понимаю, куда вставить printf внутри цикла.

void insertion_sort(FILE *fp, int ar[15])
{
  int i, j, temp;

  for (i = 0; i < 15; i++)
    printf("%d\n", ar[i]);

  for(i = 0; i < 15; i++) {
    temp = ar[i];
    for(j = i - 1; j >= 0 && ar[j] > temp; j--)
        ar[j + 1] = ar[j];
    ar[j + 1] = temp;
}

c arrays for-loop while-loop insertion-sort
person Cass Iopeia    schedule 11.02.2013    source источник
comment
вставьте printf() во внешний цикл for, так как вы хотите печатать сортируемый массив на каждом шаге.   -  person Poonam Anthony    schedule 11.02.2013
comment
твой вид вообще работает? Я думаю, вам нужно обернуть 2-й код цикла for внутри внутреннего цикла for   -  person exexzian    schedule 11.02.2013

Ответы (2)


arrow_upward
1
arrow_downward

ваша схема сортировки на самом деле сортировка выбора:

  Sort 1. 12 89 18 4 6 
  Sort 2. 4 12 89 18 6
  Sort 3. 4 6 12 89 18
  Sort 4. 4 6 12 18 89

он находит наименьшее число и помещает его в начало списка. Обычная сортировка вставками будет делать следующее:

  Sort 1. 12 89 18 4 6
  Sort 2. 12 18 89 4 6
  Sort 3. 4 12 18 89 6
  Sort 4. 4 6 12 18 89

то есть он находит, что 18 меньше 89, но больше 12, и вставляет 18 между 12 и 89, и выполняется первая итерация. Затем повторите процесс.

Вот мой код:

void insertion(int *x,int n){ // int *x - array, n- array's length
    int i,j,k,temp,elem; // i,j,k - counters, elem - to store the element at pos x[i]
    for(i=0;i<n;i++){
        elem=x[i]; // store the element
        j=i; 
        while(j>0 && x[j-1]>elem){ // the magic(actual sorting)
            x[j]=x[j-1];
            j--;
        }
        x[j]=elem;  // swap the elements
        if(i>=1){   // here begins printing every sorting step, i>=1 because first time j is not greater than 0 so it just run through the loop first time
        printf("sort %d. ",i); // printing the step
        for(k=0;k<n;k++)    // loop through array 
            printf("%d ",x[k]); // display the elements already sorted
        printf("\n"); // when the array is displayed, insert a \n so that the next display will be on a new line
        }
    }
}
person Tudor    schedule 07.09.2013
comment
как ваш код сортируется вставкой, а его код нет? Оба похожи, единственная разница заключается в типе цикла. - person SynAck; 22.06.2018

arrow_upward
0
arrow_downward

Поместите его в конец внешнего оператора for сразу после ar[j + 1] = temp; и до окончания цикла for

person Techmonk    schedule 11.02.2013