TypeScript: Implement Bubble Sort

1. Introduction

Bubble Sort is a simple sorting algorithm that works by repeatedly stepping through the list, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the list is sorted.

2. Program Overview

We will implement the Bubble Sort algorithm which works on an array of numbers. With each pass through the array, the largest element "bubbles up" to its correct position.

3. Code Program

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

    do {
        swapped = false;  // Flag to check if any swapping occurred

        for (let i = 0; i < len - 1; i++) {
            // Compare adjacent elements
            if (arr[i] > arr[i + 1]) {
                // Swap them if needed
                [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
                swapped = true;
            }
        }
        len--;  // Decrease length for optimization
    } while (swapped);  // If no two elements were swapped by inner loop, then the array is sorted

    return arr;
}

// Test the function
const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
console.log("Unsorted array:", unsortedArray);
const sortedArray = bubbleSort([...unsortedArray]);
console.log("Sorted array using Bubble Sort:", sortedArray);

Output:

Unsorted array: [ 64, 34, 25, 12, 22, 11, 90 ]
Sorted array using Bubble Sort: [ 11, 12, 22, 25, 34, 64, 90 ]

4. Step By Step Explanation

1. We declare the bubbleSort function that accepts an array of numbers arr.

2. The variable len stores the length of the array. It's used for optimization purposes to avoid checking the elements which are already in place.

3. We initialize a swapped flag to check if any swapping occurred in each pass.

4. Inside the do-while loop, for each pass through the array, we iterate over the elements and compare adjacent ones.

5. If the elements are out of order (i.e., the left element is greater than the right one), we swap them.

6. After each pass, we decrement the len variable since the highest value would have bubbled up to the last position in the array and we don't need to check it again.

7. The do-while loop continues until no more swaps are made, indicating that the array is sorted.

8. The sorted array is returned.

9. We then test the function with an unsorted array and display the result.