JavaScript Coding Test Course, Bubble Sort Program 1

Let’s learn about the essential algorithm for coding tests, Bubble Sort.

1. Problem Definition

Implement the Bubble Sort algorithm that takes an array as input and sorts it in ascending order.
Bubble Sort operates by comparing two adjacent elements and repeatedly moving the largest element to the end of the array.

Input Format

The input is an integer array with a length between 1 and 1000. Each element can have a value between -10,000 and 10,000.

Output Format

Return the array sorted in ascending order.

2. Problem Approach

Bubble Sort is a very intuitive sorting algorithm. The basic approach is to compare two adjacent elements,
and if they are not in order, swap them repeatedly until the entire array is sorted. This process is repeated for the size of the array,
and continues until no more swaps occur. This way, the largest value moves to the end of the array in each step.

2.1. Algorithm Steps

  1. Obtain the length of the array.
  2. Use two indices to compare the elements of the array.
  3. If adjacent elements are not sorted, swap them.
  4. Consider the sorting complete if no swaps occur during a full pass.
  5. Repeat the above process and ultimately return the array sorted in ascending order.

3. Bubble Sort Code Implementation

Now let’s implement the above algorithm in JavaScript. The basic Bubble Sort function is as follows. 


// Bubble Sort function implementation
function bubbleSort(arr) {
    let n = arr.length;  // Store the length of the array

    // Repeat to sort the array
    for (let i = 0; i < n - 1; i++) {
        let swapped = false;  // Variable to check if a swap has occurred

        // Compare and swap adjacent elements
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;  // Record that a swap has occurred
            }
        }

        // Exit if no swaps have occurred
        if (!swapped) break;
    }

    return arr;  // Return the sorted array
}

// Test
let testArray = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(testArray));  // [11, 12, 22, 25, 34, 64, 90]

4. Time Complexity Analysis

The time complexity of the Bubble Sort algorithm is O(n²) in the worst case. This is due to the presence of two nested loops, each proportional to the length of the array.
The best case (when the array is already sorted) is O(n). In this case, no swaps occur, and the process terminates after the first step.
Bubble Sort is generally inefficient, and it is advisable to use other algorithms (e.g., Quick Sort, Merge Sort) when sorting large datasets in practice.

4.1. Space Complexity

The space complexity of Bubble Sort is O(1). It does not use any unnecessary additional memory,
as sorting is performed within the given array.

5. Advantages and Disadvantages of Bubble Sort

Advantages

  • The algorithm is simple and easy to understand.
  • It does not have any specific requirements, so no additional memory management is necessary.
  • It works effectively with small datasets.

Disadvantages

  • The time complexity is inefficient (O(n²)).
  • Even when the array is well sorted, it must perform a complete pass, reducing efficiency.
  • It is inefficient for sorting large datasets.

6. Conclusion

In this lecture, we implemented the Bubble Sort algorithm using JavaScript.
Due to its structural simplicity, Bubble Sort is useful for educational purposes, but in real production environments, it is advisable to use more efficient algorithms.
I hope you can further develop your coding skills as you explore more complex algorithms and data structures in the future.

7. References