Typescript Bubble Sort (2024)

«PreviousNext»

Introduction

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 the list is sorted. Here's how you can implement the Bubble Sort algorithm in TypeScript:

function bubbleSort(arr: number[]): number[] { const length = arr.length; for (let i = 0; i < length - 1; i++) { for (let j = 0; j < length - i - 1; j++) { // Swap if the element found is greater than the next element if (arr[j] > arr[j + 1]) { const temp = arr[j]; arr[j] = arr[j + 1];/* w   w w  .   b  o  ok  2    s . c    o m */ arr[j + 1] = temp; } } } return arr;}// Example usage:const array = [64, 34, 25, 12, 22, 11, 90];console.log("Original Array:", array);const sortedArray = bubbleSort(array);console.log("Sorted Array:", sortedArray);

Explanation:

bubbleSort: This function takes an array of numbers as input and returns the sorted array using the Bubble Sort algorithm.
The outer loop iterates through the array from the first element to the second-to-last element. This loop represents each pass through the array.
The inner loop iterates through the array from the first element to the element before the last sorted element. This loop compares adjacent elements and swaps them if they are in the wrong order.
After each iteration of the outer loop, the largest unsorted element "bubbles up" to its correct position.
Finally, the sorted array is returned.
See Also
Bubble Sort Algorithm - GeeksforGeeks Quick Sort Algorithm - GeeksforGeeks
Example usage demonstrates sorting an array using the bubbleSort function.

top

Complexity

The time complexity of the Bubble Sort algorithm is O(n^2), where 'n' is the number of elements in the array. This is because the algorithm involves two nested loops, and in the worst-case scenario, it needs to iterate through the array multiple times.

The outer loop runs 'n' times, where 'n' is the number of elements in the array. The inner loop also runs 'n' times for each iteration of the outer loop, resulting in a total of n * (n - 1) / 2 comparisons. In Big O notation, this simplifies to O(n^2).

The space complexity of the Bubble Sort algorithm is O(1) because it only requires a constant amount of extra space for temporary variables used during the swapping process. The algorithm does not require any additional data structures that grow in proportion to the size of the input array. Therefore, the space complexity is constant, regardless of the size of the input array.

top

Illustrate

Let's use an array of 10 elements to illustrate how the Bubble Sort algorithm works step by step in TypeScript.

Consider the following array:

const array = [5, 3, 8, 1, 2, 7, 4, 10, 6, 9];

Now, let's walk through each step of the Bubble Sort algorithm applied to this array:

Initial array: [5, 3, 8, 1, 2, 7, 4, 10, 6, 9]
Pass 1:
- Comparing and swapping adjacent elements:
  - [3, 5, 1, 2, 7, 4, 8, 6, 9, 10]
  - [3, 1, 2, 5, 4, 7, 6, 8, 9, 10]
  - [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Pass 2:
- Comparing and swapping adjacent elements:
  - [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] (No swaps needed, already sorted)
Final sorted array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Here's the TypeScript code for implementing Bubble Sort and visualizing each step:

function bubbleSortStepByStep(arr: number[]): void { const length = arr.length; for (let i = 0; i < length - 1; i++) { let swapped = false;/* w  w  w .  b   o  o   k 2   s . c  o   m */ for (let j = 0; j < length - i - 1; j++) { // Swap if the element found is greater than the next element if (arr[j] > arr[j + 1]) { const temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; swapped = true; } } // If no swaps were made in this pass, the array is already sorted if (!swapped) { break; } console.log(`Pass ${i + 1}: [${arr}]`); }}// Example usage:const array = [5, 3, 8, 1, 2, 7, 4, 10, 6, 9];console.log("Initial array:", array);bubbleSortStepByStep(array.slice()); // Pass by value to avoid modifying the original arrayconsole.log("Sorted array:", array);

This code will output the array after each pass of the Bubble Sort algorithm, helping you visualize how the elements are being sorted step by step.

top

Implement

Here's how you can implement the Bubble Sort algorithm in TypeScript:

function bubbleSort(arr: number[]): number[] { const length = arr.length; // Outer loop for traversing the entire array for (let i = 0; i < length - 1; i++) { // Inner loop for comparing adjacent elements and swapping if necessary for (let j = 0; j < length - i - 1; j++) { // Swap if the element found is greater than the next element if (arr[j] > arr[j + 1]) { const temp = arr[j]; arr[j] = arr[j + 1];/*  ww   w .  b   o  o   k2  s   . c    o  m*/ arr[j + 1] = temp; } } } return arr;}// Example usage:const array = [64, 34, 25, 12, 22, 11, 90];console.log("Original Array:", array);const sortedArray = bubbleSort(array.slice()); // Pass by value to avoid modifying the original arrayconsole.log("Sorted Array:", sortedArray);