Сортировка слиянием — Вопросы с собеседований

Сортировка слиянием — это эффективный алгоритм сортировки, основанный на принципе «разделяй и властвуй». Она разбивает массив на более мелкие части, сортирует их, а затем объединяет (сливает) обратно, чтобы получить отсортированный массив. Вот основные этапы работы алгоритма:

1. Разделение: Массив рекурсивно делится пополам, пока не получится набор массивов, каждый из которых содержит только один элемент. Такие массивы по умолчанию считаются отсортированными.
2. Слияние: Пары отсортированных массивов объединяются в один, более крупный отсортированный массив. Процесс повторяется, пока все части не объединятся в один массив.
3. Слияние обратно: На каждом уровне рекурсии отсортированные части объединяются в один массив, сохраняя порядок элементов.

Пример

Рассмотрим массив [38, 27, 43, 3, 9, 82, 10]:

1. Массив делится пополам: [38, 27, 43] и [3, 9, 82, 10].
2. Затем снова делится пополам: [38, 27], [43], [3, 9], [82, 10].
3. Деление продолжается, пока не получится массивы длиной в один элемент.
4. Начинается слияние с учетом порядка: [27, 38], [3, 9], и так далее.
5. Повторное слияние и сортировка приводят к отсортированному массиву: [3, 9, 10, 27, 38, 43, 82].

Достоинства и недостатки

Плюсы:

• Эффективность для больших массивов: временная сложность O(n log n).
• Стабильная сортировка, сохраняющая порядок равных элементов.

Минусы:

• Занимает больше памяти, так как создаются временные массивы для слияния.

Сортировка слиянием часто используется в случаях, когда важна производительность для больших объемов данных.

Сортировка слиянием на Swift

Вот реализация сортировки слиянием на языке Swift:

func mergeSort(_ array: [Int]) -> [Int] {
    // Базовый случай: если массив содержит 1 или 0 элементов, он уже отсортирован
    guard array.count > 1 else { return array }
    
    // Разделение массива на две половины
    let middleIndex = array.count / 2
    let leftArray = Array(array[..<middleIndex])
    let rightArray = Array(array[middleIndex...])
    
    // Рекурсивная сортировка обеих половин
    let sortedLeft = mergeSort(leftArray)
    let sortedRight = mergeSort(rightArray)
    
    // Слияние отсортированных половин
    return merge(sortedLeft, sortedRight)
}

func merge(_ left: [Int], _ right: [Int]) -> [Int] {
    var leftIndex = 0
    var rightIndex = 0
    var sortedArray: [Int] = []
    
    // Слияние двух отсортированных массивов
    while leftIndex < left.count && rightIndex < right.count {
        if left[leftIndex] < right[rightIndex] {
            sortedArray.append(left[leftIndex])
            leftIndex += 1
        } else {
            sortedArray.append(right[rightIndex])
            rightIndex += 1
        }
    }
    
    // Добавляем оставшиеся элементы из левой и правой части
    while leftIndex < left.count {
        sortedArray.append(left[leftIndex])
        leftIndex += 1
    }
    
    while rightIndex < right.count {
        sortedArray.append(right[rightIndex])
        rightIndex += 1
    }
    
    return sortedArray
}

// Пример использования
let array = [38, 27, 43, 3, 9, 82, 10]
let sortedArray = mergeSort(array)
print(sortedArray) // [3, 9, 10, 27, 38, 43, 82]

Объяснение кода:

• Функция mergeSort: Проверяет, что массив содержит больше одного элемента. Если массив уже состоит из одного элемента или пуст, он возвращается как есть (базовый случай). Иначе массив делится пополам, и обе половины сортируются рекурсивно.
• Функция merge: Принимает два отсортированных массива и сливает их в один. Элементы добавляются в новый массив в правильном порядке, сравнивая значения из левого и правого массивов поочередно. Оставшиеся элементы из каждой половины добавляются в конец.

Этот код сортирует массив целых чисел от меньшего к большему, но его можно адаптировать для других типов данных, если они соответствуют протоколу Comparable.

Сортировка слиянием на Kotlin

fun mergeSort(array: List<Int>): List<Int> {
    // Базовый случай: если массив содержит 1 или 0 элементов, он уже отсортирован
    if (array.size <= 1) return array

    // Разделение массива на две половины
    val middleIndex = array.size / 2
    val leftArray = array.subList(0, middleIndex)
    val rightArray = array.subList(middleIndex, array.size)

    // Рекурсивная сортировка обеих половин
    return merge(mergeSort(leftArray), mergeSort(rightArray))
}

fun merge(left: List<Int>, right: List<Int>): List<Int> {
    var leftIndex = 0
    var rightIndex = 0
    val sortedArray = mutableListOf<Int>()

    // Слияние двух отсортированных массивов
    while (leftIndex < left.size && rightIndex < right.size) {
        if (left[leftIndex] < right[rightIndex]) {
            sortedArray.add(left[leftIndex])
            leftIndex++
        } else {
            sortedArray.add(right[rightIndex])
            rightIndex++
        }
    }

    // Добавляем оставшиеся элементы из левой и правой части
    while (leftIndex < left.size) {
        sortedArray.add(left[leftIndex])
        leftIndex++
    }

    while (rightIndex < right.size) {
        sortedArray.add(right[rightIndex])
        rightIndex++
    }

    return sortedArray
}

// Пример использования
fun main() {
    val array = listOf(38, 27, 43, 3, 9, 82, 10)
    val sortedArray = mergeSort(array)
    println(sortedArray) // [3, 9, 10, 27, 38, 43, 82]
}

Альтернативы сортировки слиянием

Сортировка слиянием — это один из многих алгоритмов сортировки, и у него есть несколько альтернатив, каждая из которых подходит для разных ситуаций и обладает уникальными характеристиками. Вот некоторые популярные альтернативы:

1. Быстрая сортировка (Quick Sort)

Выбирается опорный элемент (pivot), затем массив разделяется на две части: элементы меньше опорного и элементы больше. Процесс повторяется рекурсивно для каждой части.

• Преимущества: Быстрая на практике для больших массивов и имеет среднюю сложность O(n log n).
• Недостатки: Худший случай O(n^2), но его можно избежать, используя случайный выбор опорного элемента.

2. Сортировка вставками (Insertion Sort)

Массив проходит поэлементно, и каждый элемент вставляется на правильное место среди уже отсортированных элементов.

• Преимущества: Простая и эффективная для небольших массивов или почти отсортированных данных. Сложность — O(n^2).
• Недостатки: Неэффективна для больших массивов, так как требует много сравнений и перемещений.

3. Пирамидальная сортировка (Heap Sort)

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

• Преимущества: Имеет гарантированную сложность O(n log n) и не требует дополнительной памяти, как сортировка слиянием.
• Недостатки: Меньше подходит для очень больших объемов данных из-за сложности построения кучи.

4. Сортировка выбором (Selection Sort)

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

• Преимущества: Простая реализация, но на практике используется редко. Сложность O(n^2).
• Недостатки: Медленная для больших массивов, так как производит много ненужных операций.

5. Сортировка пузырьком (Bubble Sort)

Массив проходит несколько раз, каждый раз перемещая наибольший элемент в конец, «всплывая» его на нужное место.

• Преимущества: Подходит для обучения и демонстрации работы алгоритмов. Сложность — O(n^2).
• Недостатки: Один из самых медленных алгоритмов, обычно не используется на практике для реальных задач.

6. Поразрядная сортировка (Radix Sort)

Сортирует числа, начиная с младших разрядов к старшим, используя вспомогательную сортировку (обычно подсчетом).

• Преимущества: Быстрая для целых чисел или строк с фиксированной длиной, сложность O(nk), где k — количество разрядов.
• Недостатки: Подходит только для целых чисел и строк, требует дополнительной памяти.

7. Сортировка подсчетом (Counting Sort)

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

• Преимущества: Очень быстрая для массивов с небольшим диапазоном значений (линейная сложность O(n + k)).
• Недостатки: Требует дополнительной памяти и не подходит для данных с большим диапазоном значений.

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