Сортировка вставками (модифицировать алгоритм)

Question

Написать алгоритм сортировки. Но не совсем сортировка вставками, алгоритм нужно немного модифицировать. Сделала иллюстрацию после 7 прохода цикла: 8 элемент копируем в дополнительную переменную, сравниваем её с предыдущими элементами, когда находим правильную позицию, переносим туда восьмой элемент, все после него сдвигаем на 1 вправо.

void Sort(coord* ar, int s)
{
    int i, j;
    for (i = 1; i <= s; i++) { //сортування вставками
        for (j = i; j > 0 && ar[j - 1].sq > ar[j].sq; j--) {
            coord t = ar[j];
            ar[j] = ar[j - 1];
            ar[j - 1] = t;
        }
    }
}

Answer 1

Так, хотел вас довести, чтоб вы написали сами, но так как мы тут запутались... Я думаю, что от вас хотят этого:

void sort(int * a, size_t size)
{
    for(size_t i = 0; i < size-1; ++i)
    {
        // Начиная от i, ищем минимальный элемент
        int m = a[i]; size_t mi = i;
        for(size_t j = i; j < size; ++j)
            if (m > a[j]) { m = a[j]; mi = j; }

        // Копируем вправо
        for(size_t j = mi; j > i; --j)
            a[j] = a[j-1];

        // Вставляем
        a[i] = m;
    }
}

Т.е. в еще неотсортированном куске ищем минимальный элемент, сдвигаем, как у вас написано, и вставляем его - и отсортированный кусок увеличивается. Жутко неоптимально, но что с преподов взять... :)

Полный пример тут.

Answer 2

Сортирвка вставками. Это классика.

Алгоритм замечательно описан и всесторонне проанализирован в третьем томе "Искусство программирования" Д. Кнута.

void
lin_insort (int *a, int n)
{
  for (int i = 1; i < n; i++) {
    int j, t = a[i];
    // linear search desired position `j` for `a[i]` in sorted array
    for (j = i - 1; j >= 0 && t < a[j]; j--)
      a[j + 1] = a[j]; // shift right during search
    a[j + 1] = t;      // put a[i] to true position
  }
}

Вероятно это наиболее эффективный из всех простых (с временем выполнения O(N^2)) алгоритмов сортировки. Он прекрасно использует уже существующее упорядочение элементов сортируемого массива.

Идея алгоритма состоит во вставке очедного элемента в уже упорядоченную часть массива. Очевидно, что массив из одного элемента упорядочен. Последовательно берем элементы, начиная с индекса 1 и рассматриваем находящиеся перед ним, как уже отсортированный массив (т.е. проводим линейный поиск).

Запомним очередной элемент массива и перебирая элементы от конца к началу ищем позицию, в которую надо вставить новый элемент. По ходу поиска копируем элементы вправо. Найдя подходящую позицию (все элемены перед ней меньше или равны вновь вставляемому), запишем в нее запомненный ранее элемент.

На практике данный алгоритм обычно используется как составная часть многих "серьезных" алгоритмов сортировки типа "разделяй и властвуй" (QuickSort, MergeSort) с временем выполнения O(N log N) для сортировки "хвостов" (частей сортируемого массива из нескольких десятков элементов, образующихся в процессе эффективного разделения всего массива).

Иногда для поиска позиции вставки вместо линейного поиска (время O(N)) используют двоичный (он же логарифмический) поиск (время O(log N)), поскольку массив в котором ищем, уже упорядочен.
Возможно таким будет ваше следующее задание, именно поэтому сейчас вас попросили сначала найти позицию вставки, а потом сдвинуть все элементы вправо.

Сортировка вставками с двоичным поиском выглядит вот так:

// binary search the `pos` for insert `key`
// all elements to left from `pos` are less or equal the `key`
// all elements from pos to `n` are greater the `key`
int
search_pos (int key, int *a, int n)
{
  int first = 0,
    last = n,
    mid;

  while (first < last) {
    mid = first + (last - first) / 2;
    if (key < a[mid])
      last = mid;
    else
      first = mid + 1;
  }

  return first;
}

void
bin_insort (int *a, int n)
{
  for (int i = 1; i < n; i++) {
    int t = a[i],
      pos = search_pos(t, a, i); // binary search desired position for `a[i]` in sorted array
    // now shift to the right all elements between `i - 1` and `pos`
    for (int j = i; j > pos; j--)
      a[j] = a[j - 1];
    a[pos] = t;
  }
}

БЛОГ НА HUSL

Сортировка вставками (модифицировать алгоритм)

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