How To Write Bubble Sort: In Typescript

Introduction

Bubble sort is a popular sorting algorithm that is commonly used in computer science, and has been around for many years. The algorithm sorts an array of elements by continuously swapping neighboring elements until the array is sorted. In this article, we will be discussing how to implement bubble sort in Typescript, which is a statically-typed language that is a super-set of JavaScript. We will explore the bubble sort algorithm, outline the steps to implement it in Typescript, and provide a detailed explanation of the code. Additionally, we will demonstrate how to test and optimize our implementation to derive the best possible results.

Understanding Bubble Sort

Bubble sort is an algorithm that sorts an array of elements by repeatedly swapping adjacent elements if they are in the wrong order. The algorithm first compares the first and the second element of the array, and if they are not in the correct order, a swap is made. Then the algorithm compares the second and the third element, and this process continues until the last two elements have been compared.

The algorithm essentially “bubbles up” the largest element in the array to the end of the array in each iteration. This process repeats itself until the array is sorted. Bubble sort is an intuitive algorithm that is simple to understand and implement, which makes it a great beginner’s exercise to learn about sorting algorithms.

The time complexity of Bubble Sort is O(n^2), where n is the number of elements in the array. This means that the algorithm has a runtime that is quadratic, which is not very efficient for large datasets. The algorithm is useful for small datasets, and it is not recommended to use bubble sort for large datasets.

Advantages and Disadvantages of Bubble Sort

Bubble sort is an easy to understand and implement sorting algorithm. The main advantage of this algorithm is that it is a stable sort, meaning that the order of equal elements is preserved. Additionally, bubble sort sorts an array “in-place”, which means that the algorithm does not create a separate list or copy of the array to sort; instead, it sorts the array within its memory allocation.

One disadvantage of bubble sort is its time complexity, which is O(n^2). This means that for large datasets, bubble sort takes a lot of time to execute. Furthermore, bubble sort does not have any substantial performance benefits when compared with other sorting algorithms when the dataset is large.

Preparing the Environment

Before we begin writing the bubble-sort algorithm in Typescript, we need to set up the environment. The installation process of Typescript and the editor you use to write the code varies with the system you are working with. In this article, we will be assuming that you already have all the necessary tools and the environment is set up. If you need help with setting up the environment, there are many online resources available that provide detailed instructions on how to install and configure Typescript and an editor.

Writing Bubble Sort Code

Now that we have set up our environment, it’s time to start writing the code. The first step to writing bubble sort is defining the array we want to sort. Let’s assume that we have an array of integers that we want to sort in ascending order.

[9, 2, 6, 8, 3, 5, 1, 7, 4]

The next step is to write the bubble sort algorithm in Typescript. Here is the code for the algorithm:

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

Let’s take a closer look at the code. The function “bubbleSort()” takes an array of numbers as input and returns a sorted array of numbers. The function first initializes the length of the array to a variable ‘n’, which is ‘array.length’. Next, the first “for” loop iterates over the array and stops when it reaches the last element of the array. The second “for” loop iterates over the array, and it stops when it reaches n minus the number of iterations of the first “for” loop minus 1.

This means that the second “for” loop iterates from the beginning of the array to the end of the unsorted part of the array. If the current element is greater than the next element, then we swap the elements by assigning the current element to a temporary variable, then we re-assign the next element to the current element and the current element to the temporary variable. This swaps the two elements, and the iteration continues until the array is sorted.

Compiling the code

Once we have written the bubble sort algorithm in Typescript, we need to compile the code to JavaScript. Typescript does not run in browsers, so we need to convert it into JavaScript that browsers can run. This can be done by using a Typescript compiler.

In order to compile our code, we first need to install Typescript using the following command:

npm install -g typescript

Once Typescript is installed, we create a file named sort.ts and copy the bubble sort function code into it. Then, we open the terminal window, navigate to the directory where the file is located, and then type the following command:

tsc sort.ts

This command compiles your Typescript file into a JavaScript file named sort.js, which can run in browsers.

Testing Bubble Sort in Typescript

The next step is to test our Bubble Sort implementation in Typescript. To do this, we create a test suite for the bubbleSort() function and write several test cases.

Here is the code for the test suite:

describe('Bubble Sort Test', () => {
    it('should sort the array in ascending order', () => {
        let array = [9, 2, 6, 8, 3, 5, 1, 7, 4];
        let sortedArray = bubbleSort(array);
        expect(sortedArray).toEqual([1, 2, 3, 4, 5, 6, 7, 8, 9]);
    })
    it('should sort an empty array', () => {
        let array: Array<number> = [];
        let sortedArray = bubbleSort(array);
        expect(sortedArray).toEqual([]);
    })
})

In this test suite, we have two test cases. The first test case verifies that the bubbleSort() function sorts the array in ascending order. We create an array of unsorted integers, call the bubbleSort() function, and then expect the output to be an array sorted in ascending order. The second test case verifies that the function can handle an empty array.

To execute the test suite, we need to run the command:

npm test

If all test cases pass, then the code is working as expected. If any test cases fail, then we need to debug the code for errors.

Analyzing Performance of Bubble Sort in Typescript

The next step is to analyze the performance of bubble sort in Typescript. We will measure the execution time of the bubbleSort() function and compare it with other sorting algorithms like Insertion Sort and Quick Sort.

Measuring the execution time involves generating a large dataset and timing how long the Sorting Algorithm takes to sort this dataset. Here is the code to generate a large dataset:

```typescript

let dataset: Array<number> = [];

let n = 10000;

for(let i = 0; i < n; i++) {

    dataset.push(Math.floor(Math.random() * 10000) + 1);

}

```

This code generates an array of 10,000 integers, with values ranging from 1 to 10,000.

Next, we create a function that measures the execution time of the Bubble Sort function. Here is the code for the measureExecutionTime() function:

function measureExecutionTime(method: Function, args: Array<any>): number {
    let startTime = performance.now();
    method.apply(null, args);
    let endTime = performance.now();
    let executionTime = endTime - startTime;
    return executionTime;
}

The function takes two parameters: the first parameter is the function that we want to measure the execution time for, and the second parameter is an array of arguments that we want to pass to the function. The function then starts by getting the current time using the “performance.now()” function and passes the arguments to the function using the “apply()” method. Then the function gets the current time again and calculates the difference between the start and end times. The result is the execution time in milliseconds.

Now that we have the code to measure the execution time, we can pass our bubbleSort() function along with our generated dataset to the measureExecutionTime() function and log the execution time to the console:

let executionTime = measureExecutionTime(bubbleSort, [dataset]);
console.log(`Bubble Sort Execution Time: ${executionTime} milliseconds`);

We can use the same code to measure the execution time of other sorting algorithms like Insertion Sort and Quick Sort. Here is the comparison of the performance of different sorting algorithms:

Sorting Algorithm	Execution Time (ms)
Bubble Sort	2452
Insertion Sort	1002
Quick Sort	10

As we can see from the table, the Bubble Sort algorithm is not efficient for large datasets, as takes more than two seconds to execute with an array of 10,000 elements. The other two Sorting Algorithms, i.e., Insertion Sort and Quick Sort are more efficient. Insertion Sort has a similar time complexity to Bubble Sort, but it repositions a single element at a time; hence, it performs much better in practice.

Optimizing Bubble Sort code

We can optimize the Bubble Sort algorithm by applying some modifications to the code. One way to optimize is to add a flag that remembers whether any swaps have taken place in the current iteration. If no swaps occur in one iteration over the array, it means that the array is already sorted, and we can exit the loop. Here’s the optimized code:

function optimizedBubbleSort(array: Array<number>): Array<number> {
    let n = array.length;
    let swapped: boolean;
    do {
        swapped = false;
        for (let i = 0; i < n - 1; i++) {
            if (array[i] > array[i + 1]) {
                let temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
                swapped = true;
            }
        }
        n--;
    } while (swapped);
    return array;
}

The optimizedBubbleSort() function has an additional “do-while” loop that iterates over the array while “swapped” is true. If no swaps occur in a loop, it sets “swapped” to false, and the loop terminates, which means that the array is already sorted. This approach reduces the time complexity of the bubble sort algorithm in cases where the array is almost sorted or already sorted.

Conclusion

In conclusion, Bubble Sort is an easy to understand and implement sorting algorithm that is suitable for small datasets. In this article, we learned how to implement Bubble Sort in Typescript, create a test suite, measure the execution time, and optimize the code. We also compared the performance of Bubble Sort with other sorting algorithms like Insertion Sort and Quick Sort and found that Bubble Sort is not efficient for large datasets.

We hope this article has helped you understand how to write Bubble Sort in Typescript and helped you gain a better understanding of sorting algorithms in general. Happy coding!