Problem Description
Write a program that sorts a given integer array in ascending order. The elements of the array may include positive integers, negative integers, and zero. You must implement this using the basic sorting algorithm known as bubble sort.
Explanation of Bubble Sort Algorithm
Bubble sort is one of the simplest sorting algorithms, which sorts by comparing adjacent elements. This algorithm repeatedly traverses the array and compares two adjacent elements, swapping them if necessary. After traversing the array n times, the sorting is complete. In each iteration, the largest element bubbles up to the end of the array, hence the name ‘bubble sort.’
Working Process of Bubble Sort
- Let the length of the array be n, and perform n-1 iterations.
- In each iteration, traverse and compare the index i from 0 to n-1.
- Compare two adjacent elements, and if the left element is greater than the right element, swap them.
- This process consistently moves the maximum value to the end of the array.
- Repeat this process until sorting is complete.
Problem Solving Process
Step 1: Declare the Array
First, declare the array to be sorted. For example, we will use an array like the following.
let arr = [64, 34, 25, 12, 22, 11, 90];Step 2: Write the Bubble Sort Function
Write a function named bubbleSort that implements bubble sort. This function takes an array as a parameter and returns the sorted array.
function bubbleSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// Swap elements
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
Step 3: Call the Function and Output the Result
Call the function you wrote to check the result. The function can be called as follows, and the result is printed out.
let sortedArr = bubbleSort(arr);
console.log("Sorted Array:", sortedArr);
Complete Code Combination
The final code, combining all the processes, is as follows.
function bubbleSort(arr) {
let n = arr.length;
for (let i = 0; i < n - 1; i++) {
for (let j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
let arr = [64, 34, 25, 12, 22, 11, 90];
let sortedArr = bubbleSort(arr);
console.log("Sorted Array:", sortedArr);
Performance Analysis
The time complexity of bubble sort in the worst case is O(n2). This occurs because every element must be compared at least once. The average case also remains O(n2), and the best case (already sorted array) is O(n). Therefore, bubble sort can be efficient for small datasets, but it is not suitable for large data sets.
Conclusion
In this lesson, we learned how to sort an array using bubble sort. Although it’s a simple algorithm, one must be aware that repeatedly performing the same task can lead to performance degradation. Understanding such basic algorithms will serve as an important foundation when encountering more complex algorithms. In the next lesson, we will cover a more efficient sorting algorithm known as Quick Sort.