- A simple and stable algorithm that sorts by comparing and swapping adjacent elements, ideal for learning fundamentals.
- Its complexity is O(n^2), so it is inefficient on large sets and performs many unnecessary comparisons.
- Its implementation in C, Java, and Python was shown; more efficient alternatives such as quicksort and mergesort exist for larger datasets.
The bubble sort algorithm is one of the simplest and most basic algorithms used to sort items in a list. Its simplicity makes it an excellent choice for understanding the fundamental concepts of sorting algorithms. This algorithm is commonly used in applications and programs where the number of items to be sorted is small.
In this article, we will focus on implementing the bubble sort algorithm in two popular programming languages: C and Java. We will explore the steps necessary to implement this algorithm in each of these languages, analyzing the source code and providing detailed explanations.
Bubble Sort Algorithm in C and Java
The bubble sort algorithm, as the name suggests, works by comparing pairs of adjacent elements in a list and swapping them if they are in the wrong order. This process is repeated until the list is completely sorted.
How does bubble sort algorithm work in C and Java?
The bubble sort algorithm follows a simple yet effective approach to sort elements. The general working of the algorithm is shown below:
- We start with an unordered list of items.
- We iterate through the list, comparing each pair of adjacent elements.
- If the elements are in the wrong order, we swap them.
- We continue iterating over the list until it is completely sorted.
- The iteration process is repeated as many times as necessary until no more swaps are made in a complete pass.
Implementation of bubble sort algorithm in C
Below, we present the implementation of the bubble sort algorithm in the C language :
#include <stdio.h>
void bubbleSort(int array[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
int main() {
int array[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(array) / sizeof(array[0]);
bubbleSort(array, size);
printf("Array ordenado: ");
for (int i = 0; i < size; i++) {
printf("%d ", array[i]);
}
return 0;
}
In this bubble algorithm code, we have defined a function called bubbleSort which takes an array and its size as parameters. The function performs the bubble sort algorithm using two loops for. The first loop for iterates over the elements of the array, and the second loop for make the necessary comparisons and exchanges.
Finally, in the function main, we have created an example array and calculated its size. Then, we call the function bubbleSort passing the array and its size as arguments. Finally, we print the sorted array to the screen.
Implementation of bubble sort algorithm in Java
Below we present the implementation of the bubble sort algorithm in the Java language:
import java.util.Arrays;
public class BubbleSort {
public static void bubbleSort(int[] array) {
int size = array.length;
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] array = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(array);
System.out.println("Array ordenado: " + Arrays.toString(array));
}
}
In this code, we have defined a class called BubbleSort. Inside this class, we have declared a static method called bubbleSort which takes an array as a parameter. The method bubbleSort performs the bubble sort algorithm using two loops for, just like in the C implementation.
in the method main, we have created an example array and called the method bubbleSort passing the array as an argument. Finally, we use Arrays.toString(array) to print the sorted array to the console.
Implementing the bubble sort algorithm in Python
The equivalent of the Python bubble sort algorithm:
def bubble_sort(array):
size = len(array)
for i in range(size - 1):
for j in range(size - i - 1):
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]
array = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(array)
print("Array ordenado:", array)
Advantages of bubble sort algorithm
The bubble sort algorithm has some advantages, such as:
- Ease: The bubble sort algorithm is easy to understand and implement. It does not require complicated knowledge and is suitable for beginners in programming.
- Low code complexity: The code required to implement the bubble sort algorithm is relatively short and concise. This makes it a fast option for sorting a small number of elements.
Disadvantages of bubble sort algorithm
Despite its simplicity, the bubble sort algorithm also has some disadvantages:
- Inefficiency in large data setsBubble sort algorithm is not efficient in terms of runtime when dealing with large data sets. Its time complexity is O(n^2), which means that the runtime increases rapidly as the size of the data set increases.
- Number of comparisons: The bubble sort algorithm performs a large number of comparisons, even when the array is already sorted. This can lead to unnecessary loss of performance and resources.
Alternatives to the bubble sort algorithm
As data sets become larger and more complex, it is important to consider more efficient alternatives to the bubble sort algorithm. Some of the popular alternatives include:
- Insertion sort algorithm: This algorithm splits the list into a sorted part and an unsorted part, and inserts each element of the unsorted part into the correct position within the sorted part. It has a time complexity of O(n^2) in the worst case, but is more efficient than the bubble sort algorithm in most cases.
- Selection Sort Algorithm: This algorithm divides the list into an ordered part and an unordered part, and repeatedly selects the smallest element from the unordered part and places it at the end of the ordered part. It has a time complexity of O(n^2) in the worst case, but it is also more efficient than the bubble sort algorithm in most cases.
Bubble Algorithm FAQ
1. What is the time complexity of bubble sort algorithm?
The bubble sort algorithm has a time complexity of O(n^2), where “n” is the number of elements to be sorted. This means that the running time of the algorithm increases quadratically as the size of the list increases.
2. When is it appropriate to use the bubble sort algorithm?
The bubble sort algorithm is suitable when the list of items to be sorted is small. Due to its time complexity, it is not recommended for use on large data sets, as there are more efficient algorithms available.
3. Is the bubble sort algorithm stable?
Yes, Bubble Sort is a stable sorting algorithm. This means that it maintains the relative order of elements with equal keys during the sorting process.
4. What is the best alternative to the bubble sort algorithm?
The choice of the best alternative to the bubble sort algorithm depends on the context and the specific requirements of the problem. However, some more efficient algorithms, such as quicksort and mergesort , are widely used due to their lower time complexity.
5. Can the bubble sort algorithm be improved?
Yes, there are variants and optimizations of the bubble sort algorithm, such as the bidirectional bubble sort and the improved bubble sort. These optimizations reduce the number of comparisons and the number of iterations required to sort a list.
6. Where can I find more information about sorting algorithms?
You can find more information about sorting algorithms in reliable sources such as Wikipedia. Here are some useful links:
Conclusion
In this article, we have explored the bubble sort algorithm in C and Java programming languages. We have learned how this algorithm works step by step, and have seen its practical implementation in both languages. We have also discussed the advantages and disadvantages of the bubble sort algorithm, and have explored more efficient alternatives.
While the bubble sort algorithm is simple and easy to implement, it is important to consider its efficiency on larger data sets. In such cases, it is advisable to consider more efficient sorting algorithms such as insertion sort or selection sort.
We hope this article has given you a solid understanding of the bubble sort algorithm.