Сортирането чрез вмъкване е прост и ефективен алгоритъм за сортиране, който работи чрез итерация през масив и вмъкване на всеки елемент на правилното му място в сортираната част от масива. Това се прави чрез сравняване на елемента с неговите съседи и тяхното изместване, ако е необходимо, за да се направи място за вмъкнатия елемент.

В този урок ще научим как да внедрим сортиране чрез вмъкване в Swift и ще разберем как работи, като преминем през пример.

Изпълнение:

За да приложим сортиране чрез вмъкване в Swift, ще създадем функция, която приема масив от цели числа като аргумент и връща сортирана версия на този масив.

Ето кода за нашата функция за сортиране при вмъкване:

func insertionSort(_ array: [Int]) -> [Int] {
    var sortedArray = array
    for i in 1..<sortedArray.count {
        let current = sortedArray[i]
        var j = i - 1
        while j >= 0 && sortedArray[j] > current {
            sortedArray[j+1] = sortedArray[j]
            j -= 1
        }
        sortedArray[j+1] = current
    }
    return sortedArray
}

Сега нека да разберем как работи тази функция.

Първо създаваме променливо копие на входния масив и го присвояваме на променлива, наречена sortedArray. Това е така, защото ще модифицираме масива, докато го сортираме, и не искаме да модифицираме оригиналния входен масив.

След това имаме for цикъл, който итерира през всички елементи на масива, започвайки от втория елемент (индекс 1). За всяка итерация присвояваме текущия елемент на променлива, наречена current, и присвояваме индекса на предишния елемент на променлива, наречена j.

Вътре в цикъла for имаме цикъл while, който продължава докато j е по-голямо или равно на 0 и елементът с индекс j е по-голям от current. Този цикъл while измества елементите надясно, за да направи място за елемента, който се вмъква.

Накрая, извън цикъла while, вмъкваме разглеждания елемент (current) на правилното му място, като го присвояваме на индекс j+1.

Пример:

Нека разгледаме един пример, за да видим как сортирането чрез вмъкване работи върху малък масив.

Да предположим, че имаме следния масив: [5, 2, 4, 1, 3]

Първият елемент (5) вече е сортиран, така че преминаваме към втория елемент (2). Сравняваме 2 с неговите съседи (5 и 4) и откриваме, че е по-малък и от двамата. Преместваме 5 и 4 надясно, за да освободим място за 2, което води до следния масив: [2, 5, 4, 1, 3]

След това преминаваме към третия елемент (4). Сравняваме 4 с неговите съседи (5 и 2) и откриваме, че е по-голямо от 2, но по-малко от 5. Преместваме 5 надясно, за да освободим място за 4, което води до следния масив: [2, 4, 5, 1 , 3]

Продължаваме този процес, докато стигнем до крайния елемент (3). Сравняваме 3 с неговите съседи (1 и 5) и откриваме, че е по-голямо от 1, но по-малко от 5. Преместваме 5 надясно, за да освободим място за 3, което води до следния масив: [1, 2, 3, 4 , 5]

В този момент масивът е напълно сортиран и функцията връща сортирания масив: [1, 2, 3, 4, 5]

Заключение:

В заключение, сортирането чрез вмъкване е прост, но ефективен алгоритъм за сортиране, който работи чрез итерация през масив и вмъкване на всеки елемент на правилното му място в сортираната част от масива. Това е полезен алгоритъм за сортиране на малки масиви или за сортиране на масиви, които вече са частично сортирани.

За повече информация относно сортирането чрез вмъкване и други алгоритми за сортиране можете да се обърнете към документацията на Swift за сортиране и страницата на Wikipedia относно алгоритмите за сортиране.

Надявам се, че този урок е бил полезен за разбирането как да внедрите сортиране чрез вмъкване в Swift и как работи. Приятно кодиране!