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

Pigeonhole Sort

Pigeonhole sort is a sorting algorithm that works by distributing elements of an input sequence into a set of pigeonholes or buckets. It is an efficient sorting algorithm for small ranges of values where the number of elements to be sorted is roughly the same as the range of values. Pigeonhole sort is an example of a bucket sort algorithm. The pigeonhole sort algorithm works by first determining the range of values in the input sequence. This range is used to create a set of pigeonholes or buckets, each of which can hold one or more elements from the input sequence. Each element in the input sequence is then placed into its corresponding pigeonhole based on its value. If two or more elements have the same value, they can be placed in the same pigeonhole. Once all the elements have been placed into their corresponding pigeonholes, the elements are sorted within each pigeonhole. Finally, the sorted elements are combined into a single output sequence. Pigeonhole sort has a time complexity...
Post a Comment
Read more

Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a given limit. It was devised by the Greek mathematician Eratosthenes around 200 BCE, and it is still used today in various applications, such as cryptography and computer science. The basic idea of the Sieve of Eratosthenes is to eliminate all composite numbers (i.e., non-prime numbers) in a range of numbers from 2 to some upper limit. To do this, we start by marking all the numbers from 2 to the limit as potential primes. We then iterate through the list of numbers, starting with 2, and for each prime number we encounter, we mark all its multiples as composite. This process is repeated for each subsequent prime number until we reach the end of the list. At the end of this process, all the unmarked numbers that remain are primes. This is because any composite number in the list would have been marked as a multiple of some smaller prime number, and thus eliminated from the list. For example, if we sta...
Post a Comment
Read more