#50 Coding - Write a code to sort an array in javascript

Approach 1: Using the Built-in Array.prototype.sort() Method

JavaScript arrays come with a powerful built-in sort() method. This is by far the easiest and most common way to sort an array. However, there's a crucial detail to understand about its default behavior.

Default Behavior (Lexicographical Sort)

By default, the sort() method sorts elements as strings in ascending lexicographical (dictionary) order. This works fine for strings, but can lead to unexpected results with numbers.

// Sorting strings
const fruits = ["Banana", "Orange", "Apple", "Mango"];
fruits.sort();
console.log(fruits); 
// Output: ["Apple", "Banana", "Mango", "Orange"]

// Sorting numbers (default behavior is problematic)
const numbersLexical = [40, 100, 1, 5, 25, 10];
numbersLexical.sort();
console.log(numbersLexical);
// Output: [1, 10, 100, 25, 40, 5] - Not what we want for numbers!
// Why? Because '10' comes before '2' lexicographically.

Custom Sort Order with a Compare Function

To sort numbers correctly or to define any custom sort order, you must provide a compare function as an argument to sort().

• If compareFunction(a, b) returns less than 0, a comes before b.
• If compareFunction(a, b) returns 0, the order of a and b remains unchanged.
• If compareFunction(a, b) returns greater than 0, b comes before a.

Ascending Numeric Sort

const numbersAsc = [40, 100, 1, 5, 25, 10];
numbersAsc.sort((a, b) => a - b);
console.log(numbersAsc);
// Output: [1, 5, 10, 25, 40, 100]

Descending Numeric Sort

const numbersDesc = [40, 100, 1, 5, 25, 10];
numbersDesc.sort((a, b) => b - a);
console.log(numbersDesc);
// Output: [100, 40, 25, 10, 5, 1]

Sorting Objects by a Property

const people = [
    { name: "Alice", age: 30 },
    { name: "Bob", age: 25 },
    { name: "Charlie", age: 35 }
];

// Sort by age in ascending order
people.sort((a, b) => a.age - b.age);
console.log(people);
/* Output:
[
    { name: "Bob", age: 25 },
    { name: "Alice", age: 30 },
    { name: "Charlie", age: 35 }
]
*/

// Sort by name (string comparison)
people.sort((a, b) => {
    const nameA = a.name.toUpperCase(); // ignore case
    const nameB = b.name.toUpperCase(); // ignore case
    if (nameA < nameB) return -1;
    if (nameA > nameB) return 1;
    return 0; // names must be equal
});
console.log(people);
/* Output:
[
    { name: "Alice", age: 30 },
    { name: "Bob", age: 25 },
    { name: "Charlie", age: 35 }
]
*/

Approach 2: Manual Implementation of Sorting Algorithms

While .sort() is convenient, understanding how sorting algorithms work is fundamental for computer science knowledge and can be useful in specific performance-critical scenarios or when you need a custom algorithm not covered by simple comparisons.

Here, we'll implement two classic sorting algorithms: Bubble Sort and Selection Sort.

Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. It's not efficient for large datasets but is great for illustration.

function bubbleSort(arr) {
    const n = arr.length;
    let swapped;
    do {
        swapped = false;
        for (let i = 0; i < n - 1; i++) {
            // Compare adjacent elements
            if (arr[i] > arr[i + 1]) {
                // Swap them if they are in the wrong order
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]]; // ES6 array destructuring for swap
                swapped = true;
            }
        }
    } while (swapped); // Continue as long as swaps are being made
    return arr;
}

const unsortedBubble = [64, 34, 25, 12, 22, 11, 90];
console.log("Original Array (Bubble Sort):", unsortedBubble);
console.log("Sorted Array (Bubble Sort):", bubbleSort(unsortedBubble));
// Output: Sorted Array (Bubble Sort): [11, 12, 22, 25, 34, 64, 90]

Selection Sort

Selection Sort works by repeatedly finding the minimum element (considering ascending order) from the unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array:

1. The subarray which is already sorted.
2. The remaining subarray which is unsorted.

function selectionSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        // Assume the current element is the minimum
        let minIndex = i;
        // Find the minimum element in the unsorted part of the array
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // Swap the found minimum element with the first element of the unsorted part
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }
    return arr;
}

const unsortedSelection = [64, 25, 12, 22, 11];
console.log("Original Array (Selection Sort):", unsortedSelection);
console.log("Sorted Array (Selection Sort):", selectionSort(unsortedSelection));
// Output: Sorted Array (Selection Sort): [11, 12, 22, 25, 64]

Conclusion

For most practical applications in JavaScript, using the built-in Array.prototype.sort() method with a custom compare function is the most efficient and recommended approach. It's highly optimized and often implemented using algorithms like QuickSort or MergeSort (or Timsort in some environments), which have better average-case time complexities (O(n log n)) than simple O(n^2) algorithms like Bubble Sort or Selection Sort.

However, understanding how manual sorting algorithms like Bubble Sort or Selection Sort work provides valuable insight into the core logic of sorting and is excellent for learning computer science fundamentals. For competitive programming or specific niche performance requirements, you might consider implementing or adapting more advanced algorithms, but for day-to-day development, stick with the built-in solution.