Skip to main content

Bubble Sort

  

Bubble sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. It is named after the way bubbles rise to the top of a liquid, as it sorts the array by repeatedly moving the largest or smallest elements to the top of the array.

The algorithm works by iterating through the array, comparing each adjacent pair of elements and swapping them if they are in the wrong order. This process is repeated until the array is fully sorted.

Let's say we have an array of integers [5, 3, 8, 4, 2]. The first pass of the algorithm would compare 5 and 3, swap them to get [3, 5, 8, 4, 2]. It would then compare 5 and 8 and not swap them, as they are in the correct order. It would then compare 8 and 4, swap them to get [3, 5, 4, 8, 2]. It would then compare 8 and 2, swap them to get [3, 5, 4, 2, 8]. The first pass is now complete, and the largest element, 8, is at the end of the array.

The second pass would start with comparing 3 and 5, not swapping them. It would then compare 5 and 4, swap them to get [3, 4, 5, 2, 8]. It would then compare 5 and 2, swap them to get [3, 4, 2, 5, 8]. It would then compare 5 and 8, not swapping them. The second pass is now complete, and the second largest element, 5, is in its correct position.

The third pass would start with comparing 3 and 4, not swapping them. It would then compare 4 and 2, swap them to get [3, 2, 4, 5, 8]. It would then compare 4 and 5, not swapping them. It would then compare 5 and 8, not swapping them. The third pass is now complete, and the third largest element, 4, is in its correct position.

The fourth pass would start with comparing 3 and 2, swap them to get [2, 3, 4, 5, 8]. It would then compare 3 and 4, not swapping them. It would then compare 4 and 5, not swapping them. It would then compare 5 and 8, not swapping them. The fourth pass is now complete, and the array is fully sorted.

Bubble sort has a worst-case time complexity of O(n^2), which means it is not efficient for large arrays. However, it is simple to understand and implement, making it useful for small arrays or as a teaching tool.

ALGORITHM:

The algorithm of bubble sort can be described in the following steps:

  1. Start by iterating through the array from the first element to the second last element. This will be used to compare each element with its adjacent element.
  2. For each pair of adjacent elements, compare them and swap them if they are in the wrong order. In other words, if the first element is greater than the second element, swap them.
  3. After the first iteration, the largest element will be at the end of the array. Repeat the process for the remaining unsorted elements, from the first element to the second last element again.
  4. Continue this process until the entire array is sorted.
  5. The sorted array is now ready for use.

PSEUDO CODE:

Here's the algorithm of bubble sort in pseudocode:


In this algorithm, we use two nested loops to iterate through the array and compare each adjacent element. The outer loop iterates from the first element to the second last element, and the inner loop iterates from the first element to the second last element minus the number of iterations of the outer loop. This is because, after each iteration of the outer loop, the largest element is moved to the end of the array, and we don't need to compare it again.

The swap function is used to swap the two elements if they are in the wrong order. This function can be implemented using a temporary variable or without it using bitwise operators.

Bubble sort is a simple sorting algorithm, but it has a worst-case time complexity of O(n^2), which makes it inefficient for large arrays. However, it is easy to understand and implement, and can be useful for small arrays or as a teaching tool.

PYTHON CODE:

Here's an example Python code implementation of the Bubble Sort algorithm:


In this code, the bubble_sort() function takes an array arr as input and performs the bubble sort algorithm on it. The function uses two nested loops to traverse through all array elements and compare adjacent elements to determine whether a swap is needed. If a swap is needed, the function exchanges the two elements using the Python tuple syntax (a, b) = (b, a).

To test the code, we create an example array arr and call the bubble_sort() function on it. After the function completes, we print out the sorted array.

JAVA CODE:

Here's an example Java code implementation of the Bubble Sort algorithm:


In this code, the bubbleSort() method takes an integer array arr as input and performs the bubble sort algorithm on it. The method uses two nested loops to traverse through all array elements and compare adjacent elements to determine whether a swap is needed. If a swap is needed, the method exchanges the two elements using a temporary variable temp.

To test the code, we create an example integer array arr and call the bubbleSort() method on it. After the method completes, we print out the sorted array using the Arrays.toString() method to display the array as a string.

C CODE:

Here's an example C code implementation of the Bubble Sort algorithm:



In this code, the bubble_sort() function takes an integer array arr and its length n as input and performs the bubble sort algorithm on it. The function uses two nested loops to traverse through all array elements and compare adjacent elements to determine whether a swap is needed. If a swap is needed, the function exchanges the two elements using a temporary variable temp.

To test the code, we create an example integer array arr and call the bubble_sort() function on it, passing its length as a parameter. After the function completes, we print out the sorted array using a for loop to display each element in the array.

C++ CODE:

Here's an example C++ code implementation of the Bubble Sort algorithm:



In this code, the bubble_sort() function takes an integer array arr and its length n as input and performs the bubble sort algorithm on it. The function uses two nested loops to traverse through all array elements and compare adjacent elements to determine whether a swap is needed. If a swap is needed, the function exchanges the two elements using a temporary variable temp.

To test the code, we create an example integer array arr and call the bubble_sort() function on it, passing its length as a parameter. After the function completes, we print out the sorted array using a for loop to display each element in the array. We use the cout object from the iostream library to print the output.

JAVASCRIPT CODE:

Here's an example JavaScript code implementation of the Bubble Sort algorithm:


In this code, the bubbleSort() function takes an array arr as input and performs the bubble sort algorithm on it. The function uses two nested loops to traverse through all array elements and compare adjacent elements to determine whether a swap is needed. If a swap is needed, the function exchanges the two elements using a temporary variable temp.

To test the code, we create an example array arr and call the bubbleSort() function on it. After the function completes, we print out the original and sorted arrays using the console.log() method to display the arrays as strings in the console.

Comments

Post a Comment

Popular posts from this blog

Shell Sort

Shell sort is a sorting algorithm developed by Donald Shell in 1959. It is an extension of the insertion sort algorithm and is classified as an in-place comparison sort. Shell sort aims to improve the performance of insertion sort by sorting elements that are far apart from each other first, thus reducing the number of comparisons needed to sort the entire array. The algorithm works by first dividing the array into smaller subarrays, each containing elements that are a certain gap apart. The gap is typically initialized to be the length of the array divided by 2, and is then halved in each iteration until it becomes 1. The subarrays are then sorted using insertion sort, which sorts elements within each subarray by comparing adjacent elements and swapping them if they are in the wrong order. The key idea behind Shell sort is that insertion sort performs poorly on arrays that are almost sorted, but works well on small arrays. By sorting the subarrays with larger gaps first, the algorithm...
Post a Comment
Read more

Comb Sort

Comb sort is a sorting algorithm that was first proposed by Włodzimierz Dobosiewicz in 1980. The algorithm is a variation of bubble sort, and it is designed to improve upon the performance of bubble sort by using a larger gap between elements during the comparison phase of the algorithm. The basic idea behind comb sort is to compare elements that are separated by a large gap, and gradually reduce the gap between elements until the gap is equal to 1. The gap between elements is known as the "comb" in comb sort, and it is initially set to be the size of the input array being sorted. The size of the comb is then reduced by a factor known as the shrink factor, which is typically set to 1.3. During each pass of the algorithm, elements that are separated by the current gap are compared and swapped if they are out of order. The gap between elements is then reduced by the shrink factor, and the process is repeated until the gap is equal to 1. Once the gap is equal to 1, the algorithm...
Post a Comment
Read more