Sorting Algorithm, you need to know

Sorting algorithms are essential in computer science, playing a key role in organizing data for efficient searching, visualization, and more. In this post, we’ll dive into three common sorting algorithms: Bubble Sort, Selection Sort, and Merge Sort. We’ll cover how each works, its implementation in JavaScript, and when to use each one.

1. Bubble Sort

Bubble Sort is one of the simplest sorting algorithms, where the largest unsorted element “bubbles” to its correct position with each iteration.

How Bubble Sort Works:

1. Start at the beginning of the array.
2. Compare each pair of adjacent elements.
3. Swap them if they are in the wrong order.
4. Repeat the process for the rest of the array until it’s fully sorted.

JavaScript Implementation:

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

console.log(bubbleSort([100, -40, 500, -124, 0, 21, 7]));
// Output: [-124, -40, 0, 7, 21, 100, 500]

Time Complexity:

• Worst-case: O(n²) – when the array is sorted in reverse order.
• Best-case: O(n) – when the array is already sorted.

When to Use Bubble Sort:

• Suitable for small datasets or when you want a simple sorting algorithm.
• Not efficient for large datasets due to its O(n²) time complexity.

2. Selection Sort

Selection Sort repeatedly selects the smallest (or largest, depending on sorting order) element from the unsorted portion and places it at the beginning.

How Selection Sort Works:

1. Divide the array into a sorted and an unsorted region.
2. Find the smallest element in the unsorted region.
3. Swap it with the first element of the unsorted region.
4. Move the boundary between sorted and unsorted regions one step forward.
5. Repeat until the array is sorted.

JavaScript Implementation:

function selectionSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let minIndex = i;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex !== i) {
            let temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
    return arr;
}

console.log(selectionSort([100, -40, 500, -124, 0, 21, 7]));
// Output: [-124, -40, 0, 7, 21, 100, 500]

Time Complexity:

• Worst-case and Best-case: O(n²) – it performs the same number of comparisons regardless of the initial arrangement of the array.

When to Use Selection Sort:

• Suitable for small datasets where simplicity is preferred over performance.
• Less efficient for large datasets.

3. Merge Sort

Merge Sort is a “divide and conquer” algorithm that splits the array into smaller sub-arrays, sorts them, and merges them back together.

How Merge Sort Works:

1. Recursively split the array into halves until each sub-array contains a single element.
2. Merge the sorted sub-arrays back together.

JavaScript Implementation:

function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    const middle = Math.floor(arr.length / 2);
    const left = arr.slice(0, middle);
    const right = arr.slice(middle);

    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    const result = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }

    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

console.log(mergeSort([100, -40, 500, -124, 0, 21, 7]));
// Output: [-124, -40, 0, 7, 21, 100, 500]

Time Complexity:

• Worst-case and Best-case: O(n log n) – due to the “divide and conquer” nature of the algorithm.

When to Use Merge Sort:

• Ideal for large datasets where time complexity is a concern.
• Performs well for stable sorting requirements.

Conclusion

Each sorting algorithm has its strengths and weaknesses:

• Bubble Sort is simple but inefficient for large arrays.
• Selection Sort is also simple but works similarly inefficiently on large datasets.
• Merge Sort is more efficient for large datasets due to its O(n log n) complexity.

Choose the appropriate sorting algorithm based on the size of your data and performance requirements. Understanding these sorting algorithms will improve your problem-solving skills and deepen your knowledge of fundamental computer science concepts.