Answering what the hell a Sorting Algorithm is

For today’s lesson, I am going to give you a teaser of a Notion doc I have.

What is a Sorting Algorithm?

A sorting algorithm is a method for arranging elements of a list in a certain order, like numerical or alphabetical. It's like organizing books on a shelf by their titles or numbers. Common orders are ascending (from small to large) or descending (from large to small).

Use in Interviews for Data Structures amp; Algorithms (DSA)

In interviews, sorting algorithms are used to assess a candidate's understanding of different approaches to organizing data. They're crucial because:

• Sorting helps simplify problem-solving (e.g., finding a median, searching more efficiently).
• Different sorting algorithms have different efficiencies, important for performance.
• Questions might involve modifying or improving a basic sorting algorithm.

Before we continue, it’s important to know the divide and conquer algorithm and how it works in conjunction with the examples below.

What is the Divide and Conquer Algorithm?

Divide and conquer is a powerful algorithm principle that breaks a problem into smaller subproblems that are similar to the original problem, but simpler to solve. These subproblems are solved independently, and their solutions are then combined to give a solution to the original problem.

In other words:

1. Divide: Break the problem into several subproblems that are smaller instances of the same problem.
2. Conquer: Solve each subproblem recursively; if they are small enough, simply solve for them.
3. Combine: Merge the solutions of the subproblems to get a solution to the original problem.

Example in TypeScript: Bubble Sort

Here's an example of the Bubble Sort algorithm in TypeScript using divide and conquer:

function bubbleSort(arr: number[]): number[] {
    let n = arr.length;
    let swapped: boolean;

    do {
        swapped = false; // Initially, no elements are swapped

        // Iterate over the array
        for (let i = 1; i < n; i++) {
            // Compare adjacent elements
            if (arr[i - 1] > arr[i]) {
                // Swap elements if they are in the wrong order
                [arr[i - 1], arr[i]] = [arr[i], arr[i - 1]];
                swapped = true; // Mark that a swap occurred
            }
        }

        // Reduce the array length since the last element is already in place
        n--;

    } while (swapped); // Continue if a swap happened in the previous iteration

    return arr; // The array is now sorted
}

const myArray = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(myArray)); // Outputs: [11, 12, 22, 25, 34, 64, 90]        

In this example:

• The variable swapped is used to track whether any elements were swapped during a pass through the array.
• If no swaps occur, then the array must be sorted, and the algorithm can stop early, enhancing efficiency.
• The inner for loop performs the actual comparisons and swaps.
• With each pass through the array, the highest (or largest) unsorted element 'bubbles up' to its correct position, hence the name 'Bubble Sort'.

If you like this kind of content, please subscribe to the newsletter: https://thenewdevs.substack.com/p/answering-what-the-hell-a-sorting