В мире алгоритмов: Сортировка Вставками

От автора
Данная статья рассматривает один из алгоритмов сортировки массивов. Она предназначена для новичков или же для тех кто по каким-то причинам не знаком с данным алгоритмом. Исправления и поправки только приветствуются:)

Теория
Сортировка вставками (Insertion Sort) — это простой алгоритм сортировки. Суть его заключается в том что, на каждом шаге алгоритма мы берем один из элементов массива, находим позицию для вставки и вставляем. Стоит отметить что массив из 1-го элемента считается отсортированным.

Словесное описание алгоритма звучит довольно сложно, но на деле это самая простая в реализации сортировка. Каждый из нас, не зависимо от рода деятельности, применял алгоритм сортировки, просто не осознавал это:) Например когда сортировали купюры в кошельке — берем 100 рублей и смотрим — идут 10, 50 и 500 рублёвые купюры. Вот как раз между 50 и 500 и вставляем нашу сотню:) Или приведу пример из всех книжек — игра в карточного «Дурака». Когда мы тянем карту из колоды, смотрим на наши разложенные по возрастанию карты и в зависимости от достоинства вытянутой карты помещаем карту в соответствующее место. Для большей наглядности приведу анимацию из википедии.
Сортировка вставками

Реализация
Прежде чем приступить к реализации определимся с форматом входных данных — для примера это будет массив целочисленных (int) значений. Нумерация элементов массива начинается с 0 и заканчивается n-1. Сам алгоритм реализуем на языке C++. Итак приступим…
Основной цикл алгоритма начинается не с 0-го элемента а с 1-го, потому что элемент до 1-го элемента будет нашей отсортированной последовательностью (помним что массив состоящий из одного элемента является отсортированным) и уже относительно этого элемента с номером 0 мы будем вставлять все остальные. Собственно код:

for(int i=1;i<n;i++)     
	for(int j=i;j>0 && x[j-1]>x[j];j--) // пока j>0 и элемент j-1 > j, x-массив int
			swap(x[j-1],x[j]);        // меняем местами элементы j и j-1

Реализация сортировки очень проста, всего 3 строчки. Функция swap меняет местами элементы x[j-1] и x[j]. Вложенный цикл ищет место для вставки. Рекомендую запомнить этот алгоритм, чтобы в случае необходимости написать сортировку не позориться сортировкой пузырьком:)

Анализ производительности
Сортировка вставками имеет сложность n2, количество сравнений вычисляется по формуле n*(n-1)/2. Для доказательства был написан следующий код:
void Sort(int* arr,int n){
	int counter=0;
	for(int i=1;i<n;i++){
		for(int j=i; j>0 && arr[j-1]>arr[j];j--){
			counter++;
			int tmp=arr[j-1];
			arr[j-1]=arr[j];
			arr[j]=tmp;
		}
	}
	cout<<counter<<endl;
}

Количество перестановок для 100 элементов:
Результат работы программы
Итак при n=100 количество перестановок равно 4950, а не 10000 если бы мы высчитывали по формуле n2. Имейте это ввиду при выборе алгоритма сортировки.

Эффективность
Сортировка вставками наиболее эффективна когда массив уже частично отсортирован и когда элементов массива не много. Если же элементов меньше 10 то данный алгоритм является лучшим. Не зря в быстрой сортировке (оптимизация Боба Седжвика) используется алгоритм сортировки вставками как вспомогательный, но об этом алгоритме мы поговорим позже…
Поделиться публикацией
Похожие публикации
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама
Комментарии 24
  • 0
    А еще лучше, если массив полностью уже отсортирован=)

    Я бы посмотрел на реализацию пирамидальной сортировки на разных языках. Особенно транслируемых.
    • 0
      Я думаю если не заплюют и до пирамидальной дойдём) На каких языках вы бы хотели её видеть?)
    • +6
      Начинать надо было с пузырька. Сортировка вставками сразу это как-то негуманно совсем.
      • –2
        Не думал что с пузырьком могут возникнуть у кого-то трудности, но если нужно могу рассмотреть и её)
      • +8
        Сортировка вставками имеет сложность n2 на практике же приблизительное количество перестановок вычисляется по формуле n2/2.
        Вы забываете про O. В данном случае временная сложность O(n2), то есть время работы T(n) ограничено функцией C*n2 для некоторого C > 0.
        Для доказательства был написан следующий код:
        Этот код ничего не доказывает, у вас просто частный случай. Доказывается эта формула в общем виде совсем не так.
        • –2
          А почему при разных n количество перестановок n2/2? Я просто еще студент, учусь еще)
          • 0
            Или вы имеете ввиду что c=1/2?
            • 0
              Имеется ввиду, что вы взяли определенное n с определенной перестановкой элементов и делаете очень «громкие» выводы. Возьмите и сделайте 1000 тестов. При разных n и при разной степени «сортированности» последовательности. Тогда вам явно станет более все наглядно. А лучше конечно почитать трушную теорию — Кормена например, или что-то в этом духе.
              • –1
                Сделал много тестов, рандомные числа, и худший случай для сортировки — массив отсортированный в обратном порядке. Выяснил вот что, там не n^2/2 там n*(n-1)/2 сравнений. Читаю именно Кормена, Бентли уже прочёл… Кто не верит пусть проверит, зря вы мне карму минусуете…
                • +1
                  Вам хотели объяснить, что есть такое понятие, как асимптотическая сложность алгоритма. Она записывается для данного алгоритма так: O(n^2). Это означает, что рост количества реальный действий, совершаемых программой — T(n) — не может расти быстрее, чем функция C*n^2, где C — некоторая константа.
                  Вообще говоря, при учете сложности алгоритмов на эту константу нечасто обращают внимание. Потому что важна именно зависимость скорости работы от размера входных данных. Для алгоритмов сортировок, основанных на сравнении элементов, доказано, что не может существовать алгоритма со сложностью лучшей, чем n*log(n).
                  Опять же, взять в сравнение эту самую сортировку вставками и, например, HeapSort. У второго алгоритма эта константа намного больше — сами операции более сложные, плохо используется кеш, и т.д. Но тем не менее, HeapSort лучше именно тем, что при достаточно больших значениях n он превзойдет InsertionSort именно за счет того, что его асимптотическая сложность O(n*log(n)), и это при достаточно большом n «компенсирует» сколько угодно большую константу этого алгоритма.
                  • 0
                    Спасибо большое, за объяснение) В оценках путаюсь бывает — Тетта и О…
                    • 0
                      Для алгоритмов сортировок, основанных на сравнении элементов, доказано, что не может существовать алгоритма со сложностью лучшей, чем n*log(n).

                      А можно поподробней про доказательство? Т.е., понятно, что алгоритмов с лучшей асимптотикой пока не придумали, но интересно было посмотреть именно на формальное доказательство.
                      • +1
                        Т.е., понятно, что алгоритмов с лучшей асимптотикой пока не придумали

                        И не придумают, ведь доказано, что минимум это O(nlogn)

                        Правда есть алгоритмы которые работают за время O(n), вроде BucketSort и Radix Sort. Но они не могут отсортировать произвольный набор данных, а только определенный, заранее известный.

                        посмотреть именно на формальное доказательство

                        classes.soe.ucsc.edu/cmps102/Fall01/solutions7.pdf — Смотрите проблему N2
                        • +1
                          Если в двух словах — представим, что нам нужно отсортировать массив из N элементов, для простоты условимся, что все ключи попарно различны. Эти элементы поступают на вход алгоритма сортировки в виде одной из N! различных перестановок этих элементов. Фактически, задачей алгоритма сортировки является нахождение такой перестановки, применение которой к входной перестановке ее отсортирует. Причем для каждой из возможных входных перестановок существует 1 единственная перестановка, переводящая входной массив в отсортированный.
                          Алгоритм сортировки постепенно «уточняет» необходимую перестановку так, чтобы в итоге осталась одна единственная, сортирующая именно эту входную последовательность. Здесь можно представить работу алгоритма как дерево принятия решений — на каждом шаге множество возможный перестановок «делится» на те, которые точно не подходят и те, среди которых есть искомая. Т.е., например, до первого шага алгоритма у нас есть N! вариантов, а после первого шага — t1,1 вариантов, и исключены t1,2 вариантов. Причем t1,1 + t1,2 = N!.. На втором шаге уже t1,1 делится на t2,1 и t2,2 так что t2,1 + t2,2 = t1,1 и т.д. В этом дереве каждый лист соответствует одной перестановке — следовательно, их N! штук. Дерево строго бинарно. Если h — высота этого дерева, значит, на i-м уровне дерева не более, чем 2^(i — 1) вершин. И всего вершин — не более 2^h. Так получается неравенство 2^h >= N!.. После логарифмирования обеих частей можно получить следующую цепочку: h >= log_2(N!) >= (N/2) * log_2(N/2). Т.е. высота дерева не может расти медленнее, чем N*log_2(N), получается, h = O(N*log_2(N)) — это и является нижней оценкой на высоту дерева.

                          Немного скомкано получилось, уж извините, но идея, надеюсь, понятна.
                          • 0
                            Спасибо, идею понял, а статья из комментария выше объясняет некоторые части математики.
            • 0
              Сложность алгоритмов сортировки определяется не количеством операций перестановки, а количеством операций сравнения элементов.
              • +4
                Мне кажется что эта статься не для хабра. (и пусть это останется моим имхо) (P.S. сори немного промахнулся, надо было на уровень выше)
                • –3
                  Я просто не нашёл на хабре ничего подобного, и решил что было бы здорово брать какой-либо алгоритм и рассматривать его подробно)
                  • 0
                    Ну стоит начать с того, что объем статьи — не для подробного описания. Алгоритмы сортировок (за исключением чего-то нестандартного) разжеваны по всему интернету и поиск не составляет никакого труда…
                    Ну а на постскриптум, статья оригинал (во всяком случае анимация именно оттуда)- куда более широко отвечает на поставленный вопрос (и даже на русской вики всё понятно)=)
                    • 0
                      Ну статью я сам писал, а анимация из вики и я это не скрываю=)
                    • +1
                      Писать — это хорошо: как минимум развивает умение грамотно формулировать свои мысли. То, что вас раскритиковали — тоже хорошо: именно критика и указание на ошибки дают вектор для дальнейшего развития. Однако, перед написанием сделайте пару вещей:

                      1. Подумайте, интересено ли будет пользователям читать вашу статью. Вы пишете в первую очередь для сообщества, а не для себя. Иначе зачем вообще это нужно?
                      2. Хорошо изучите материал. Если вы завели тему, будьте готовы поддержать разговор на неё.
                      3. Определите для себя цель написания статьи. Возможно, вы хотите рассказать сообществу о новом, малоизвестном алгоритме; возможно, собрать воедино и структурировать информацию о чём-то, чтобы другие люди могли прочитать одну статью вместо 2-х десятков противоречивых и устаревших страниц по теме; возможно, обоснованно высказать своё мнение. Но должна быть цель, некий посыл, с которым вы пришли.

                      У вас же получается статья о сортировке, которую все и так хорошо знают, анализ алгоритмов вы пока ещё не очень освоили и поддержать разговор на хорошем уровне ещё не получается, а цель статьи остаётся неясной. Сообщество старается селекционировать наиболее полезные и интересные материалы и отсеивать остальные, поэтому вас и минусуют. Создавайте хороший, полезный материал, и вас будут плюсовать ;)
                      • +1
                        Я новичёк на Хабре, это моя первая статья, обязательно будем расти… Целью было как раз объединить информацию об алгоритме в одну статью… Я на самом деле благодарен за критику, она обоснована и помогает развиваться) Всем комментаторам спасибо:) Задумка была начать с простого алгоритма и в следующих статьях рассматривать алгоритмы всё сложнее и сложнее. Когда ты можешь написать статью об алгоритме он у тебя невольно остаётся в памяти) Я не считаю этот алгоритм вершиной сложности, наоборот решил начать с простого. Моя фамилия Дроздов и это «В мире алгоритмов», в следующий раз всё будет лучше:)
                • +2
                  Для тех камрадов, кто любит танцы и программирование: Insert-sort with Romanian folk dance

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.