Сортиране чрез вмъкване

Има много различни начини за сортиране. При изпълнението на сортиране чрез пряка селекция подмасивът в началото на масива е сортиран, но подмасивът в края не е. Сортиране чрез пряка селекция сканира несотирания подмасив за следващия елемент, който да се включи в сортирания.

Ето още един начин да мислиш за сортирането. Представи си, че играеш на карти. Държиш картите в ръката си и те са подредени. Раздаващият ти дава точно една нова карта. Трябва да я поставиш на точното място, така че картите ти да останат подредени. При сортирането с пряка селекция всеки елемент, който добавяш във вече подредения подмасив, е не по-малък от елементите във вече подредения подмасив. Но в нашия пример с картите новата карта може да е по-малка от някои от картите, които вече държиш, затова ти я сравняваш с всяка от вече подредените карти в ръката си, докато намериш точното място, на което да я поставиш. Поставяш новата карта на правилното място и отново в ръката си имаш напълно подредени карти. След което раздаващият ти дава нова карта и ти повтаряш същата процедура. След това нова карта, и нова карта и така нататък, докато раздаващият спре да ти дава карти.

Това е идеята на сортирането чрез вмъкване. Изпълнение на цикъл върху позиции в масива, като се започне с индекс 1. Всяка нова позиция е като нова карта, подадена ти от раздаващия, и ти трябва да я вмъкнеш в правилното място в сортирания подмасив отляво на тази позиция. Ето визуализация на стъпките, през които се минава:

От гледна точка на масиви, представи си, че подмасивът от индекс 0 до индекс $5$‍ вече е сортиран, а ние искаме да вмъкнем елемент на индекс 6 в този сортиран подмасив, така че подмасивът от индекс 0 до индекс 6 е сортиран. Ето как започваме:

И ето как трябва да изглежда подмасивът, когато сме готови:

За да вмъкнем елемент в позиция 6 в подмасив на ляво, ние многократно го сравняваме с елементите отляво, тръгвайки от дясно наляво. Нека наречем елемент в позиция 6 ключ. Всеки път, когато откриваме, че ключът е по-малък от елемента отляво, преместваме този елемент една позиция надясно, тъй като знаем, че ключът ще трябва да отиде отляво на този елемент. Ще трябва да направим две неща, за да работи тази идея: трябва да имамепреместване, операция, която премества елемент една позиция надясно, и трябва да запазим стойността на ключа на отделно място (така, че тя не се презаписва от елемента непосредствено вляво). В нашия пример нека да сложим елемента с индекс 6 в променлива наречена key:

Сега сравненяваме key с елемента на позиция 5. Намираме, че key (5) е по-малък от елемента на позиция 5 (13), затова преместваме този елемент на позиция 6:

Забележи, че операцията преместване просто копира елемент една позиция надясно. След това сравняваме key с елемента в позиция 4. Намираме, че key (5) е по-малък от елемента на позиция 4 (10), и преместваме и този елемент:

След това сравняваме key с елемента на позиция 3 и плъзгаме и този елемент:

Същото се случва с елемента на позиция 2:

Сега стигаме до елемента на позиция 1, който има стойност 3. Този елемент е по-малък от key, затова не го плъзгаме. Вместо това слагаме key непосредствено вдясно от този елемент (тоест, в позиция 2), последно плъзнат надясно. Резултатът е, че масивът от индекс 0 до индекс 6 е сортиран:

Сортирането чрез вмъкване многократно вмъква елемент в лявата част на сортиран подмасив. В началото можем да кажем, че подмасив, съдържащ само индекс 0, е сортиран, тъй като той съдържа само един елемент, а как може един елемент да не е сортиран по отношение на себе си? Той трябва да е сортиран. Нека да разгледаме пример. Това е нашият първоначален масив:

Тъй като подмасив, съдържащ само индекс 0, е нашият първоначално сортиран подмасив, първият ключ е в индекс 1. (Ще покажем сортирания подмасив в червено, ключа в жълто, а тази част на масива, която все още трябва да обработим, в синьо.) Вмъкваме ключа отляво на сортирания подмасив:

Сега сортираният подмасив е от индекс 0 до индекс 1, а новият ключ е на индекс 2. Вмъкаме го отляво на сортирания подмасив:

Продължаваме така като всеки елемент от масива на свой ред става ключ и го поставяме от ляво на сортирания подмасив:

След като вмъкнем най-десния елемент в масива, сме сортирали целия масив:

Две от ситуациите, на които попаднахме в нашия пример, заслужават повече внимание: когато вмъкнатият ключът е по-малък от всички елементи отляво (както когато добавим ключове 2 и 3), и когато той е по-голям или равен на всички елементи отляво (както когато добавим ключ 13). В първия случай всеки елемент в подмасива отляво на ключа се плъзга с една позиция надясно, и трябва да спрем, когато стигнем левия край на масива. Във втория случай при първото сравнение на ключа с елемента отляво намираме, че ключът е вече в правилната си позиция по отношение на всички елементи на ляво; няма елементи за преместване и ключът се връща обратно на позицията, от която е започнал.

Основната стъпка в сортирането чрез вмъкване е да се направи място в масива, където да се постави текущата стойност, която се съхранява в променливата key. Както видяхме по-горе, ние минаваме през подмасив отляво на първоначалната позиция на key, от дясно наляво, като плъзгаме всеки елемент, който е по-голям от key с една позиция надясно. След като открием елемент, който е по-малък от key, или равен на key, спираме плъзгането и копираме key в освободената позиция надясно от този елемент. (Разбира се, позицията не е наистина освободена, но елементът ѝ е плъзнат надясно.) Тази диаграма показва идеята:

Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.