сортировка вставок во введении в алгоритм - PullRequest
Новая
       14

сортировка вставок во введении в алгоритм

1 голос
/ 26 января 2012

во 2-м издании "Введение в алгоритм" я обнаружил псевдокод сортировки вставок 

INSERTION-SORT(A)
1   for j <- 2 to length[A]
2       do key <- A[j]
3          //Insert A[j] into the sorted sequence A[1 □ j - 1].
4          i <- j - 1
5          while i > 0 and A[i] > key
6           do A[i+1] <- A[i]
7              i <- i -1
8          A[i + 1] <- key

, но не могу понять, как здесь работает своп.

Я думаю, что нужна операция свопингакак это 

INSERTION-SORT(A)
1   for j <- 2 to length[A]
2       do key <- A[j]
3          //Insert A[j] into the sorted sequence A[1 □ j - 1].
4          i <- j - 1
5          while i > 0 and A[i] > key
6           do temp <- A[i+1]
7              A[i+1] <- A[i]
8              A[i] <- temp
9              i <- i -1
10         A[i + 1] <- key

я что-то не так понял?пожалуйста помогите

Ответы [ 4 ]

2 голосов
/ 26 января 2012

То, что происходит при сортировке вставкой, не является свопом.

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

1 голос
/ 31 декабря 2017

Код выполняет «многократный обмен», точнее, поворот k элементов на одну позицию на месте. Это займет одну вспомогательную переменную key, как это делает своп.

1 голос
/ 31 декабря 2017

У меня такая же проблема. Ниже приведен код на C, который правильно реализует приведенный выше псевдокод.

Сложность была в том, что псевдокод использует нотации массивов, основанные на 1, в отличие от большинства языков программирования! 

#include <stdio.h>

int main(void)
{
  int A[] = { 50, 20, 10, 40, 60, 30 };
  int j, key, len, i;
  len = (sizeof(A)) / (sizeof(A[0]));

    for (j = 1; j < 6; j++) {  <-- Change here
      key = A[j];
      // Insert key into the sorted sequence A[1 .. j - 1].
      i = j - 1;
      while (i >= 0 && A[i] > key) {  <-- Change here
          A[i + 1] = A[i];
          i--;
      }
      A[i + 1] = key;
    }

    for (int z = 0; z < len; z++) {
       printf("%d ", A[z]);
    }
   printf("\n");
 }
1 голос
/ 26 января 2012

но я не могу понять, как здесь работает своп.

Нет, это не так.

Значение уже сохранено в начале.

Сохраняет j, а затем сдвигает все остальные элементы, пока не найдет нужное место

...