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)
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 # Exit if there were no exchanges
end
return arr
end
# Usage example
arr = [64, 34, 25, 12, 22, 11, 90]
println("Before sorting: ", arr)
println("After bubble sorting: ", bubble_sort!(copy(arr)))
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
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
# Usage example
println("After sorting by inserts: ", insertion_sort!(copy(arr)))
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
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
# Usage example
println("After sorting by selection: ", selection_sort!(copy(arr)))
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
In [ ]:
function quick_sort!(arr, low=1, high=length(arr))
if low < high
pi = partition!(arr, low, high) # The partition index
quick_sort!(arr, low, pi-1)
quick_sort!(arr, pi+1, high)
end
return arr
end
function partition!(arr, low, high)
pivot = arr[high] # Support element
i = low - 1 # The index of the smaller element
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
# Usage example
println("After a quick sort: ", quick_sort!(copy(arr)))
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
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
# Adding the remaining elements
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
# Usage example
println("After the merge sort: ", merge_sort!(copy(arr)))
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
In [ ]:
function heap_sort!(arr)
n = length(arr)
# Building a heap (rearranging an array)
for i in n÷2:-1:1
heapify!(arr, n, i)
end
# Extracting items from the heap
for i in n:-1:2
arr[1], arr[i] = arr[i], arr[1] # Moving the current root to the end
heapify!(arr, i-1, 1) # Calling heapify on a reduced heap
end
return arr
end
function heapify!(arr, n, i)
largest = i # Initialize the largest one as the root
l = 2i # The left child
r = 2i + 1 # The right child
# If the left child is larger than the root
if l <= n && arr[l] > arr[largest]
largest = l
end
# If the right child is larger than the largest
if r <= n && arr[r] > arr[largest]
largest = r
end
# If the largest is not the root
if largest != i
arr[i], arr[largest] = arr[largest], arr[i]
heapify!(arr, n, largest) # Recursively transform the affected subtree
end
end
# Usage example
println("After the pyramid sorting: ", heap_sort!(copy(arr)))
Performance Comparison
Let's compare the running time of different algorithms on a large array.:
In [ ]:
# Connecting libraries
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
In [ ]:
# Generating a large array of random numbers
Random.seed!(123)
big_arr = rand(1:1000, 1000)
println("Comparison of sorting time for an array of 10,000 elements:")
@time bubble_sort!(copy(big_arr)) # Very slow!
@time insertion_sort!(copy(big_arr)) # Faster than a bubble, but still slow
@time selection_sort!(copy(big_arr)) # Similarly
@time quick_sort!(copy(big_arr)) # Quickly
@time merge_sort!(copy(big_arr)) # Quickly
@time heap_sort!(copy(big_arr)) # Quickly
@time sort!(copy(big_arr)); # Built-in sorting
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).
In [ ]:
# Using the built-in sorting
arr = [64, 34, 25, 12, 22, 11, 90]
println("Built-in sorting: ", sort!(copy(arr)))
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.