6. Сортировка

6. Сортировка

O(N²): пузырьковая сортировка, сортировка выбором, сортировка вставками
O(NlogN): быстрая сортировка, сортировка слиянием, сортировка кучей

6. 1. Пузырьковая сортировка — O(N²)

Сравнивает первую цифру массива со значением следующей цифры, и если предыдущее значение больше, позиция цифры меняется. Повторите длину массива, чтобы сравнить индексы сзади.

func boubbleSort (_ data:[Int],_ n:Int) -> [Int]{
    var data = data
    for i in 0...n-2 {
        let last = n-i
        for j in 0...last-1 {
            if data[j] > data[j+1] {
                let temp = data[j]
                data[j] = data[j+1]
                data[j+1] = temp
            }
        }
    }
    return data
}
boubbleSort([7,5,4,2,3,9], 5)

6. 2. Сортировка вставками — O(N²)

Если значение в самом конце массива меньше, чем значение предыдущей цифры на месте, поменяйте местами два значения. Если измененное значение меньше предыдущего, поменяйте местами два значения. Если обмен не производится, повторите со значением в конце массива.

func insertionSort (_ data:[Int],_ n:Int) -> [Int]{
    var data = data
    var end = n-1
    
    for i in (0...n-1).reversed() {
        for j in (0...end).reversed() {
            if data[i] < data[j] {
                let temp = data[i]
                data[i] = data[j]
                data[j] = temp
            }
        }
        end -= 1
    }
    return data
}
insertionSort([7,5,4,2,3,9], 6)

6. 3. Сортировка выбором — O(N²)

Найдите наибольшее значение в массиве и замените его значением в конце массива. Затем повторите с массивом, кроме последнего.

func selectionSort (_ data:[Int],_ n:Int) -> [Int]{
    var data = data
    var end = n-1
    for i in 0...end {
        var largestIndex = 0
        for j in 0...end {
            if data[j] > data[largestIndex] {
                largestIndex = j
            }
        }
        let temp = data[largestIndex]
        data[largestIndex] = data [n-1-i]
        data[n-1-i] = temp
        end -= 1
    }
    return data
}
selectionSort([7,5,4,2,3,9], 6)

6. 4. Быстрая сортировка — O(NlogN)

Быстрая сортировка – лучший метод сортировки среди нескольких методов сортировки.
(Используются методы рекурсии, разделения и квантизации.)

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

var data = [5,2,7,4,1,10,6,3,8,9]
    
func quickSort(_ left: Int,_ right: Int){
    if (left < right){
        var pivot = partition(left, right)
        quickSort(left, pivot-1)
        quickSort(pivot+1, right)
    }
}
    
func partition(_ left: Int,_ right: Int) -> Int {
    var i = left
    for j in (left + 1)...(right + 1) {
        if data[j] < data[left] {
            i += 1
            (data[i], data[j]) = (data[j], data[i])
        }
    }
    (data[i], data[left]) = (data[left], data[i])
    return i
}
quickSort(0,9)

6. 5. Сортировка слиянием — O(NlogN)

• Разделить: разделяет массив, в котором хранятся данные, пополам.
• Conquer: упорядочить каждый массив циклически
• Слияние: объединение двух массивов

Базовая сортировка слиянием начинается с двух отсортированных данных A, B и массива C для слияния двух данных. Переменные i, j и count используются для отображения текущего расположения данных сравнения массива A, B и C, а начальное значение устанавливается в исходное положение каждой переменной.

func merge(left:[Int],right:[Int]) -> [Int] {
    var mergedList = [Int]()
    var left = left
    var right = right
    
    while left.count > 0 && right.count > 0 {
        if left.first! < right.first! {
            mergedList.append(left.removeFirst())
        } else {
            mergedList.append(right.removeFirst())
        }
    }
 
    return mergedList + left + right
}
 
func mergeSort(list:[Int]) -> [Int] {
    guard list.count > 1 else {
        return list
    }
    
    let leftList = Array(list[0..<list.count/2])
    let rightList = Array(list[list.count/2..<list.count])
    
    return merge(left: mergeSort(list:leftList), right: mergeSort(list:rightList))
}
print(mergeSort(list:[5,2,7,4,1,10,6,3,8,9]))