How do you sort an array without using sort()?

Sorting an array without using the built-in sort() function can be a fundamental exercise in understanding algorithms and data structures. There are several sorting algorithms that can be implemented manually, each with its own advantages and disadvantages. In this response, I will discuss a couple of common sorting algorithms: Bubble Sort and Quick Sort. Additionally, I will provide practical examples, best practices, and common mistakes to avoid when implementing these algorithms.

Bubble Sort

Bubble Sort is one of the simplest sorting algorithms. It works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. The process is repeated until the list is sorted.

Implementation

function bubbleSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap arr[j] and arr[j + 1]
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

Best Practices

• Always check if the array is already sorted to avoid unnecessary iterations.
• Consider implementing an optimized version that stops the algorithm if no swaps were made during a pass.

Common Mistakes

• Forgetting to handle edge cases, such as empty arrays or arrays with one element.
• Not understanding the time complexity, which is O(n^2) in the average and worst cases.

Quick Sort

Quick Sort is a more efficient sorting algorithm that uses a divide-and-conquer approach. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays according to whether they are less than or greater than the pivot.

Implementation

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let pivot = arr[arr.length - 1];
    let left = [];
    let right = [];
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return [...quickSort(left), pivot, ...quickSort(right)];
}

Best Practices

• Choose a good pivot to improve performance, such as using the median of the first, middle, and last elements.
• Implement in-place partitioning to reduce space complexity.

Common Mistakes

• Not handling duplicate elements properly, which can lead to infinite recursion.
• Failing to consider the worst-case time complexity of O(n^2) when the pivot is poorly chosen.

In conclusion, sorting an array without using the built-in sort() function can be accomplished through various algorithms. Understanding the strengths and weaknesses of each algorithm is crucial for selecting the right one based on the specific requirements of the task at hand. By following best practices and avoiding common pitfalls, you can implement efficient sorting algorithms effectively.