Алгоритмы сортировки
Автор
yurevАлгоритмы сортировки в Engee: от теории к практике
Сортировка — одна из фундаментальных операций в компьютерных науках, имеющая множество практических применений. В этой статье мы рассмотрим основные алгоритмы сортировки, их реализацию на языке Engee, проанализируем их временную сложность и особенности работы.
Алгоритмы сортировки можно разделить на несколько категорий:
- Сравнительные сортировки (основаны на попарном сравнении элементов)
- Несравнительные сортировки (используют специальные свойства данных)
- Рекурсивные сортировки (используют принцип "разделяй и властвуй")
- Итеративные сортировки (работают за счёт последовательных проходов по данным)
1. Сортировка пузырьком (Bubble Sort)
Логика:
- Попарно сравнивает соседние элементы
- Если порядок неправильный — меняет их местами
- Процесс повторяется, пока массив не будет отсортирован
Сложность: O(n²) в худшем случае, O(n) в лучшем (уже отсортированный массив)
In [ ]:
function bubble_sort!(arr)
n = length(arr)
for i in 1:n-1
swapped = false
for j in 1:n-i
if arr[j] > arr[j+1]
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = true
end
end
!swapped && break # Выход, если обменов не было
end
return arr
end
# Пример использования
arr = [64, 34, 25, 12, 22, 11, 90]
println("До сортировки: ", arr)
println("После сортировки пузырьком: ", bubble_sort!(copy(arr)))
2. Сортировка вставками (Insertion Sort)
Логика:
- Массив условно делится на отсортированную и неотсортированную части
- Каждый новый элемент вставляется в правильную позицию в отсортированной части
Сложность: O(n²) в худшем случае, O(n) в лучшем
In [ ]:
function insertion_sort!(arr)
for i in 2:length(arr)
key = arr[i]
j = i - 1
while j >= 1 && arr[j] > key
arr[j+1] = arr[j]
j -= 1
end
arr[j+1] = key
end
return arr
end
# Пример использования
println("После сортировки вставками: ", insertion_sort!(copy(arr)))
3. Сортировка выбором (Selection Sort)
Логика:
- Массив делится на отсортированную и неотсортированную части
- На каждом шаге находится минимальный элемент в неотсортированной части
- Этот элемент добавляется в конец отсортированной части
Сложность: O(n²) в любом случае
In [ ]:
function selection_sort!(arr)
n = length(arr)
for i in 1:n-1
min_idx = i
for j in i+1:n
if arr[j] < arr[min_idx]
min_idx = j
end
end
arr[i], arr[min_idx] = arr[min_idx], arr[i]
end
return arr
end
# Пример использования
println("После сортировки выбором: ", selection_sort!(copy(arr)))
4. Быстрая сортировка (Quick Sort)
Логика (рекурсивная):
- Выбирается опорный элемент (pivot)
- Массив разбивается на две части: элементы меньше pivot и больше pivot
- Рекурсивно применяется к обеим частям
Сложность: O(n log n) в среднем, O(n²) в худшем случае
In [ ]:
function quick_sort!(arr, low=1, high=length(arr))
if low < high
pi = partition!(arr, low, high) # Индекс разбиения
quick_sort!(arr, low, pi-1)
quick_sort!(arr, pi+1, high)
end
return arr
end
function partition!(arr, low, high)
pivot = arr[high] # Опорный элемент
i = low - 1 # Индекс меньшего элемента
for j in low:high-1
if arr[j] < pivot
i += 1
arr[i], arr[j] = arr[j], arr[i]
end
end
arr[i+1], arr[high] = arr[high], arr[i+1]
return i + 1
end
# Пример использования
println("После быстрой сортировки: ", quick_sort!(copy(arr)))
5. Сортировка слиянием (Merge Sort)
Логика (рекурсивная):
- Массив разбивается на две примерно равные части
- Каждая часть рекурсивно сортируется
- Отсортированные части сливаются в один массив
Сложность: O(n log n) в любом случае
In [ ]:
function merge_sort!(arr)
if length(arr) > 1
mid = length(arr) ÷ 2
left = arr[1:mid]
right = arr[mid+1:end]
merge_sort!(left)
merge_sort!(right)
i = j = k = 1
while i <= length(left) && j <= length(right)
if left[i] < right[j]
arr[k] = left[i]
i += 1
else
arr[k] = right[j]
j += 1
end
k += 1
end
# Добавляем оставшиеся элементы
while i <= length(left)
arr[k] = left[i]
i += 1
k += 1
end
while j <= length(right)
arr[k] = right[j]
j += 1
k += 1
end
end
return arr
end
# Пример использования
println("После сортировки слиянием: ", merge_sort!(copy(arr)))
6. Пирамидальная сортировка (Heap Sort)
Логика:
- Построение max-кучи из массива
- Максимальный элемент (корень) меняется с последним элементом
- Уменьшаем размер кучи и повторяем процесс
Сложность: O(n log n) в любом случае
In [ ]:
function heap_sort!(arr)
n = length(arr)
# Построение кучи (перегруппировка массива)
for i in n÷2:-1:1
heapify!(arr, n, i)
end
# Извлечение элементов из кучи
for i in n:-1:2
arr[1], arr[i] = arr[i], arr[1] # Перемещаем текущий корень в конец
heapify!(arr, i-1, 1) # Вызываем heapify на уменьшенной куче
end
return arr
end
function heapify!(arr, n, i)
largest = i # Инициализируем наибольший как корень
l = 2i # Левый дочерний
r = 2i + 1 # Правый дочерний
# Если левый дочерний больше корня
if l <= n && arr[l] > arr[largest]
largest = l
end
# Если правый дочерний больше largest
if r <= n && arr[r] > arr[largest]
largest = r
end
# Если largest не корень
if largest != i
arr[i], arr[largest] = arr[largest], arr[i]
heapify!(arr, n, largest) # Рекурсивно преобразуем затронутую поддерево
end
end
# Пример использования
println("После пирамидальной сортировки: ", heap_sort!(copy(arr)))
Сравнение производительности
Давайте сравним время работы разных алгоритмов на большом массиве:
In [ ]:
using Random, BenchmarkTools
# Генерируем большой массив случайных чисел
Random.seed!(123)
big_arr = rand(1:1000, 1000)
println("Сравнение времени сортировки для массива из 10000 элементов:")
@time bubble_sort!(copy(big_arr)) # Очень медленно!
@time insertion_sort!(copy(big_arr)) # Быстрее пузырька, но всё ещё медленно
@time selection_sort!(copy(big_arr)) # Аналогично
@time quick_sort!(copy(big_arr)) # Быстро
@time merge_sort!(copy(big_arr)) # Быстро
@time heap_sort!(copy(big_arr)) # Быстро
@time sort!(copy(big_arr)); # Встроенная сортировка
Встроенная сортировка в Engee
Engee предоставляет встроенную оптимизированную функцию сортировки sort!(), которая в большинстве случаев использует комбинацию быстрой сортировки и сортировки вставками (для маленьких массивов).
In [ ]:
# Использование встроенной сортировки
arr = [64, 34, 25, 12, 22, 11, 90]
println("Встроенная сортировка: ", sort!(copy(arr)))
Выбор алгоритма сортировки
- Малые массивы (n < 50): сортировка вставками
- Средние массивы: быстрая сортировка или сортировка слиянием
- Большие массивы: пирамидальная сортировка или встроенная sort!()
- Особые случаи:
- Почти отсортированные данные: сортировка вставками
- Ограниченный диапазон значений: подсчётная сортировка
- Очень большие данные, не помещающиеся в память: внешняя сортировка
Вывод
Мы рассмотрели основные алгоритмы сортировки, их реализацию на Engee и особенности работы:
- Простые сортировки (O(n²)): пузырьком, вставками, выбором — хороши для обучения и маленьких массивов
- Эффективные сортировки (O(n log n)): быстрая, слиянием, пирамидальная — используются в реальных задачах
- Встроенная сортировка Engee — оптимальный выбор для большинства практических случаев
Правильный выбор алгоритма сортировки может значительно повлиять на производительность вашей программы, особенно при работе с большими объемами данных.