Понимание сортировки вставки

Программы состоят из множества блоков внутри себя, а эти блоки, в свою очередь, состоят из других блоков. Говоря рекурсивно, мы могли бы добраться до основных единиц информации, с которыми работает процессор: 0 и 1. Я объяснил в этом посте, что будет двоичными числами. В конце концов, процессор всегда работает с двоичной информацией, но с представлением высокого уровня. Буквально информация — это 0 и 1, но она имеет разное значение, когда мы собираем ее в некоторые множества и в соответствии с операциями.

Наконец, каждый атомарный блок этой информации называется битом, а набор из 8 битов — байтом. В конце концов, почему 8? Потому что изначально 8 = 2³!
Любая операция, связанная с множествами или числовыми преобразованиями в компьютере, всегда будет выражаться в основании 2. Условно говоря, его легче вычислять и проверять, поскольку компьютер работает с информацией в двоичной форме. Поэтому 1 байт = 2³ бита, килобайт — 2^10 байт, килобайт — 10³ байт (различие между килобайтом и килобайтом объясняется здесь).

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

int *array = new int[5]{2, 4, 5, 6, 7};
std::cout << array[2] << std::endl;

// 5
Войдите в полноэкранный режим Выход из полноэкранного режима

Представления кода в этой заметке, если не указано явно, будут выражены на C++

Помните, что массив начинается с индекса 0!
Некоторые языки программирования предоставляют возможность построения ассоциативного массива, т.е. вместо нумерации индекса, индекс именуется, например, в PHP:

$exampleArray = array(
  'joão' => 'maria',
  'joaquim' => 'jose'
);

echo $exampleArray['joao'];

// maria
Войдите в полноэкранный режим Выход из полноэкранного режима

Много раз мы можем столкнуться с ситуацией, когда данные дезорганизованы внутри этого массива, а когда это очень большой массив, то у нас возникает большая проблема, если мы собираемся использовать линейный поиск на нем (O(n)). Представьте, что массив содержит 500 элементов. Таким образом, в худшем случае будет 500 сравнений, необходимых для поиска элемента. Мы можем использовать бинарный поиск, эффективность которого в худшем случае составляет O(log(n)), тогда, в худшем случае, сравнений будет 9!

Но есть и другая проблема: чтобы применить бинарный поиск к массиву, он должен быть расположен в порядке возрастания. Если он неорганизован или организован не в порядке возрастания, то есть вероятность, что поиск никогда не найдет своего результата.

В этом случае приходится прибегать к алгоритму сортировки, или Sorting Algorithm. В этой статье я расскажу о сортировке вставками, одной из самых простых и с одной из самых низких эффективностей (O(n²) в худшем случае), но она является базовой для понимания других алгоритмов.

Чтобы немного проиллюстрировать проблему эффективности этого алгоритма, предположим, что у нас есть массив из 10 позиций, расположенных в порядке убывания. Чтобы отсортировать его, потребуется 100 сравнений. Проблема становится только хуже, чем больше элементов и чем более дезорганизован массив.

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

Давайте реализуем его поэтапно.

Прежде всего, рассмотрим массив с одним элементом. В этом случае автоматически массив уже заказан, отсюда мы можем расширять наши горизонты, постепенно. Для случая, когда у нас есть массив с 5 элементами, например, если гипотетически удалить последние 4 элемента, то останется только первый, и он уже будет упорядочен. Следующим шагом будет вставка следующего элемента, его упорядочивание, затем следующего и так далее. Затем мы формируем петлю:

// Para arrays convencionais, quando passa-se os mesmos a funções
// Eles decaem para ponteiros. Não temos uma função específica 
// para saber o seu tamanho e não podemos usar o sizeof, então 
// o tamanho tem que ser passado como argumento para a função

int *insertionSort(int *arr, int arrLength){
  for(int i = 1; i < arrLength; i++){

  // ...

  }
}
Войдите в полноэкранный режим Выход из полноэкранного режима

Так что же мы делаем? Мы пропускаем первый элемент и итерируем над следующими, так как первый элемент мы можем считать отсортированным. Следующие мы будем вставлять в массив, состоящий из 1 элемента, и он будет расти. Следующим шагом будет хранение элемента, который мы собираемся сравнить с уже отсортированными, в отдельном адресе памяти, поскольку нам придется перемещать элементы по массиву.

for(int i = 1; i < arrLength; i++){
  int cur = arr[i];
  int index2Compare = i - 1;
}
Войдите в полноэкранный режим Выход из полноэкранного режима

Переменная index2Compare будет принимать индекс элемента, расположенного точно перед элементом, который мы сравниваем, чтобы начать делать сравнения.

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

for(int i = 1; i < arrLength; i++){
  // ...
  int index2Compare = i - 1;

  while(index2Compare >= 0 && arr[index2Compare] > cur){
    //...
  }
}
Войдите в полноэкранный режим Выход из полноэкранного режима

Итак, в данном случае мы говорим, что цикл будет расширяться при двух условиях:

  • До тех пор, пока сравниваемый индекс больше или равен 0, так что мы не достигаем индекса -1 массива;
  • До тех пор, пока элемент, предшествующий текущему элементу, больше текущего элемента;

Если оба условия выполнены, то мы поменяем местами предыдущий элемент, переместим его на один индекс вперед и перейдем к сравнению следующего перед ним элемента:

for(int i = 1; i < arrLength; i++){
  // ...
  while(index2Compare >= 0 && arr[index2Compare] > cur){
    arr[index2Compare + 1] = arr[index2Compare];
    index2Compare--;
  }
}
Войдите в полноэкранный режим Выход из полноэкранного режима

Если по какой-то случайности любое из вышеперечисленных условий не выполняется, что произойдет? Тогда мы достигли идеальной точки для вставки нашего элемента, но помните, что с каждой такой субитерацией мы уменьшаем index2Compare на -1, поэтому позиция для вставки нашего элемента будет в index2Compare + 1:

for(int i = 1; i < arrLength; i++){
  // ...
  while(index2Compare >= 0 && arr[index2Compare] > cur){
    // ...
  }
  arr[index2Compare + 1] = cur;
}
Войдите в полноэкранный режим Выход из полноэкранного режима

Помните, мы начали с объявления, что функция возвращает указатель на int, так давайте вернем тот же массив:

int *insertionSort(int *arr, int arrLength){
  //...
  return arr;
}
Войдите в полноэкранный режим Выход из полноэкранного режима

Полный код этой реализации приведен ниже:

int *insertionSort(int *arr, int arrLength){

  for(int i = 1; i < arrLength; i++){

    int cur = arr[i];
    int index2Compare = i - 1;

    while(index2Compare >= 0 && arr[index2Compare] > cur){
        arr[index2Compare + 1] = arr[index2Compare];
        index2Compare--;
    }

    arr[index2Compare + 1] = cur;
  }

  return arr;
}
Войдите в полноэкранный режим Выход из полноэкранного режима

Ниже приведена небольшая программа для проверки этой реализации:

#include <iostream>

using namespace std;

int *insertionSort(int *arr, int arrLength){

  for(int i = 1; i < arrLength; i++){

    int cur = arr[i];
    int index2Compare = i - 1;

    while(index2Compare >= 0 && arr[index2Compare] > cur){
        arr[index2Compare + 1] = arr[index2Compare];
        index2Compare--;
    }

    arr[index2Compare + 1] = cur;
  }

  return arr;
}

int main()
{
    int arrLength = 9;

    // dependendo do compilador, o mesmo pode exigir que você
    // especifique qual o tamanho do array, mesmo declarando
    // os elementos ahead of time. O gcc aceita a sintaxe 
    // abaixo. O onlineGDB exige que você especifique o tamanho 
    // do array
    int *arrExample = new int[]{6, 3, 9, 1, 0, 9, 2, 9, 5};


    int *sorted = insertionSort(arrExample, arrLength);

    for(int i = 0; i < arrLength; i++){
        cout << sorted[i] << endl;
    }

    return 0;
}
Войдите в полноэкранный режим Выход из полноэкранного режима
0
1
2
3
5
6
9
9
9


...Program finished with exit code 0
Press ENTER to exit console.
Войдите в полноэкранный режим Выход из полноэкранного режима

Оцените статью
devanswers.ru
Добавить комментарий