22 Июл


2017

Сортировка вставкой. Insert sort.

Продолжая тему прокачки нейронок по средствам изучения (потоврения) алгоритмов. Также является достаточно простым алгоритмом, имеет сложность O(n^2) хотя по факту должен выполняться все же быстрее сортиовки выбором и пузырьком. Данный алгоритм я не изучал, сама идея достаточно понятна, достаточно взглянуть на статью википедии.

А вот при реализации меня ввело немного в ступор смещение, в моей голове все складывалось в 3 цикла ^_^. Поэтому все же пришлось переписать все на листочек, прочитать хабр и перебрать на бумаге последовательно решение. Тем не менее:

void InsertSort(int* arr, int len){
    int tmp;
    for (int i=1; i < len; ++i){
        for (int j=i; j > 0 && arr[j - 1] > arr[j]; --j){
            tmp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = tmp;
        }
    }
}

Хотя изначально я думла писать функцию которая ищет 2 числа между которыми нужно вставить текущий элемент, а все остальные элементы смещать на 1 позицию вправо.

Ну и видосик еще более наглядно емонстрирующий работы алгоритма.

 

Решил также открыть на гитхабе ветку куда буду выкладывать разобранные алгоритмы (пока все еще на qt, хотя возможно в будущем перейду на джаву)

сортировка