Sorting algorithms in Engee: from theory to practice

Sorting is one of the fundamental operations in computer science, which has many practical applications. In this article, we will look at the basic sorting algorithms, their implementation in the Engee language, and analyze their time complexity and operational features.
Sorting algorithms can be divided into several categories:

Comparative sorting (based on pairwise comparison of elements)
Incomparable sorting (uses special data properties)
Recursive sorting (uses the principle of "divide and conquer")
Iterative sorting (works by sequential passes through the data)

1. Bubble Sort

Logic:

Compares neighboring elements in pairs
If the order is wrong, swap them.
The process repeats until the array is sorted.

Complexity: O(n2) in the worst case, O(n) in the best (already sorted array)

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)))

До сортировки: [64, 34, 25, 12, 22, 11, 90]
После сортировки пузырьком: [11, 12, 22, 25, 34, 64, 90]

2. Insertion Sort

Logic:

The array is conditionally divided into sorted and unsorted parts
Each new element is inserted into the correct position in the sorted part

Difficulty: O(n2) at worst, O(n) at best

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)))

После сортировки вставками: [11, 12, 22, 25, 34, 64, 90]

3. Selection Sort

Logic:

The array is divided into sorted and unsorted parts
At each step there is a minimum element in the unsorted part.
This element is added to the end of the sorted part.

Difficulty: O(n2) anyway

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)))

После сортировки выбором: [11, 12, 22, 25, 34, 64, 90]

4. Quick Sort

Logic (recursive):

The pivot is selected
The array is divided into two parts: elements smaller than the pivot and larger than the pivot
Recursively applied to both parts

Difficulty: O(n log n) on average, O(n2) in the worst case

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)))

После быстрой сортировки: [11, 12, 22, 25, 34, 64, 90]

5. Merge Sort

Logic (recursive):

The array is divided into two approximately equal parts
Each part is recursively sorted
The sorted parts merge into one array.

Difficulty: O(n log n) in any case

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)))

После сортировки слиянием: [11, 12, 22, 25, 34, 64, 90]

6. Pyramid sorting (Heap Sort)

Logic:

Building a max heap from an array
The maximum element (root) changes with the last element.
Reduce the size of the heap and repeat the process

Difficulty: O(n log n) in any case

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)))

После пирамидальной сортировки: [11, 12, 22, 25, 34, 64, 90]

Performance Comparison

Let's compare the running time of different algorithms on a large array.:

# Подключение библиотек
neededLibs = ["Random", "BenchmarkTools"]
for lib in neededLibs
    try
        eval(Meta.parse("using $lib"))
    catch ex
        Pkg.add(lib)
        eval(Meta.parse("using $lib"))
    end
end

# Генерируем большой массив случайных чисел
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));           # Встроенная сортировка

Сравнение времени сортировки для массива из 10000 элементов:
  0.001370 seconds (346 allocations: 122.703 KiB)
  0.000199 seconds (3 allocations: 7.883 KiB)
  0.000579 seconds (3 allocations: 7.883 KiB)
  0.000080 seconds (3 allocations: 7.883 KiB)
  0.000224 seconds (4.00 k allocations: 202.836 KiB)
  0.000095 seconds (3 allocations: 7.883 KiB)
  0.000042 seconds (8 allocations: 16.078 KiB)

Built-in sorting in Engee

Engee provides a built-in optimized sorting function sort!(), which in most cases uses a combination of quick sort and insertion sort (for small arrays).

# Использование встроенной сортировки
arr = [64, 34, 25, 12, 22, 11, 90]
println("Встроенная сортировка: ", sort!(copy(arr)))

Встроенная сортировка: [11, 12, 22, 25, 34, 64, 90]

Choosing a sorting algorithm

Small arrays (n<50): insertion sort
Medium Arrays: quick sort or merge sort
Large arrays: pyramid sorting or built-in sort!()
Special cases:

Almost sorted data: insertion sort
Limited range of values: counting sort
- Very large data that does not fit in memory: external sorting

Conclusion

We have reviewed the main sorting algorithms, their implementation on Engee, and the specifics of their work.:

Simple sorting (O(n2)): bubble, insert, select — good for training and small arrays
Efficient sorting (O(n log n)): fast, merge, pyramid — used in real-world tasks
Built—in Engee sorting is the optimal choice for most practical cases

Choosing the right sorting algorithm can significantly affect the performance of your program, especially when working with large amounts of data.