Using a sorting algorithm to compare solutions in different languages

One of the most common sorting algorithms is named QuickSort.

QuickSort is an efficient, comparison-based sorting algorithm that uses the divide-and-conquer approach to sort elements. It’s one of the most commonly used algorithms because it performs well in practice, typically with a time complexity of O(n log n) ) for most inputs.

Here’s a simple breakdown of how it works:

• Choose a Pivot:
  The algorithm selects one element from the array as the pivot. This pivot helps in partitioning the array into two parts. There are various strategies for choosing the pivot (e.g., picking the first, last, middle, or a random element).

• Partitioning:
  Rearrange the array so that all elements smaller than the pivot come before it, and all elements greater than the pivot come after it. The pivot will end up in its correct position in the sorted array.

• Recursively Apply:
  Apply the same process to the sub-arrays on the left and right of the pivot, sorting them until the entire array is sorted.

Lets take a look at how this would look in Javascript:

function quickSort(arr) {
    // Base case: arrays with 0 or 1 element are already "sorted"
    if (arr.length <= 1) {
        return arr;
    }

    // Choose a pivot (we'll use the last element in this case)
    const pivot = arr[arr.length - 1];
    
    // Arrays to store elements smaller or greater than the pivot
    const left = [];
    const right = [];

    // Partitioning: move elements smaller than pivot to 'left', greater to 'right'
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    // Recursively sort the left and right sub-arrays, then combine them with the pivot
    return [...quickSort(left), pivot, ...quickSort(right)];
}

// Example usage
const unsortedArray = [38, 27, 43, 3, 9, 82, 10];
const sortedArray = quickSort(unsortedArray);

console.log(sortedArray);  // Output: [3, 9, 10, 27, 38, 43, 82]

Lets take a look at how this would look in Elixir:

defmodule Sorter do
  def quicksort([]), do: []
  def quicksort([pivot | rest]) do
    # Partition the list into two: elements less than and greater than the pivot
    {left, right} = Enum.split_with(rest, fn x -> x < pivot end)
    
    # Recursively quicksort the left and right parts and combine them with the pivot
    quicksort(left) ++ [pivot] ++ quicksort(right)
  end
end

# Example usage
unsorted_list = [38, 27, 43, 3, 9, 82, 10]
sorted_list = Sorter.quicksort(unsorted_list)

IO.inspect(sorted_list)  # Output: [3, 9, 10, 27, 38, 43, 82]

Lets take a look at how this would look in Rust.

fn quicksort(arr: &mut [i32]) {
    if arr.len() <= 1 {
        return;
    }

    // Choose a pivot (here, we use the last element)
    let pivot_index = partition(arr);

    // Recursively sort the left and right parts
    quicksort(&mut arr[0..pivot_index]);
    quicksort(&mut arr[pivot_index + 1..]);
}

fn partition(arr: &mut [i32]) -> usize {
    let pivot_index = arr.len() - 1;
    let pivot = arr[pivot_index];

    // `i` tracks the index where elements smaller than the pivot should go
    let mut i = 0;
    for j in 0..pivot_index {
        if arr[j] < pivot {
            arr.swap(i, j); // Move the smaller element to the front
            i += 1;
        }
    }

    // Move the pivot into its correct place
    arr.swap(i, pivot_index);
    i
}

fn main() {
    let mut arr = [38, 27, 43, 3, 9, 82, 10];
    println!("Unsorted array: {:?}", arr);
    
    quicksort(&mut arr);
    
    println!("Sorted array: {:?}", arr);
}

This is a great example of regardless of the processing power or use case for a given language, how the syntax reads can have a great impact.

Elixir reads just so elegantly and concise. Its such a joy to work in.