Tutorial Playlist
58 Lessons1. Data Structure
2. Types of Linked Lists
3. Array vs Linked Lists in Data Structure
4. Stack vs. Queue Explained
5. Singly Linked List
6. Circular doubly linked list
7. Circular Linked List
8. Stack Implementation Using Array
9. Circular Queue in Data Structure
10. Dequeue in Data Structures
11. Bubble Sort Algorithm
Now Reading
12. Insertion Sort Algorithm
13. Shell Sort Algorithm
14. Radix Sort
15. Counting Sort Algorithm
16. Trees in Data Structure
17. Tree Traversal in Data Structure
18. Inorder Traversal
19. Optimal Binary Search Trees
20. AVL Tree
21. Red-Black Tree
22. B+ Tree in Data Structure
23. Expression Tree
24. Adjacency Matrix
25. Spanning Tree in Data Structure
26. Kruskal Algorithm
27. Prim's Algorithm in Data Structure
28. Bellman Ford Algorithm
29. Ford-Fulkerson Algorithm
30. Trie Data Structure
31. Floyd Warshall Algorithm
32. Rabin Karp Algorithm
33. What Is Dynamic Programming?
34. Longest Common Subsequence
35. Fractional Knapsack Problem
36. Greedy Algorithm
37. Longest Increasing Subsequence
38. Matrix Chain Multiplication
39. Subset Sum Problem
40. Backtracking Algorithm
41. Huffman Coding Algorithm
42. Tower of Hanoi
43. Stack vs Heap
44. Asymptotic Analysis
45. Binomial Distribution
46. Coin Change Problem
47. Fibonacci Heap
48. Skip List in Data Structure
49. Sparse Matrix
50. Splay Tree
51. Queue in Data Structure
52. Stack in Data Structure
53. Time and Space Complexity
54. Linked List in Data Structure
55. Stack And Queue: Roles & Functions
56. Doubly Linked List
57. Strongly Connected Components
58. Bucket Sort Algorithm
The bubble sort algorithm is a simple way to sort items in order. It continuously swaps adjacent items that are in the wrong order. This process continues until the list is sorted.
Being a crucial part of data structure learning, it shows how to organize data efficiently. The algorithm uses a series of steps to ensure each item moves to its correct position.
To apply Bubble Sort, you need to follow a set of instructions known as pseudocode. This guide helps programmers write the algorithm in any programming language. Understanding the pseudocode is key to implementing the Bubble Sort.
One important aspect of Bubble Sort is its time complexity. This tells us how the sorting time increases with the size of the list. Despite being slower than other algorithms, Bubble Sort has its uses in certain scenarios where simplicity is more valuable than speed.
The bubble sort algorithm is an easy way to sort items. It compares pairs of items and exchanges them if needed. This method works by moving through the list multiple times. Each pass ensures that the highest unsorted item finds its correct place.
Bubble Sort fits well within data structures, especially when learning sorting basics. It's not the fastest method, but it's easy to understand. You will often see it used as an introduction to sorting algorithms.
The steps for the implementation of Bubble Sort are simple. Compare two adjacent items, and swap them if they are in the wrong order. Repeat this process until the whole list is sorted. This algorithm shows how simple swaps can organize data.
Understanding bubble sort time complexity helps us know how fast it sorts items under different conditions. Generally, Bubble sorting is slower than other sorting methods. However, its simplicity makes it valuable for beginners.
The Bubble Sort Algorithm plays an important role in data organization. It is a simple method used for many programming tasks. By comparing adjacent items and swapping them if they are out of order, it sorts lists or arrays. This approach is useful for small datasets or educational purposes, showcasing basic sorting logic.
For example, if you have a list of numbers like [5, 3, 8, 4, 2], Bubble Sort arranges them in ascending order. After a few passes, the list becomes [2, 3, 4, 5, 8]. This method shines in scenarios where simplicity and understandability are more important than speed. It is a first step for beginners before they move on to more complex sorting techniques.
To use the Bubble Sort algorithm in a data structure, follow these steps:
For example, consider the list [4, 2, 3, 1]. In the first pass, we compare 4 and 2, swapping to get [2, 4, 3, 1]. We continue comparing and swapping: [2, 3, 4, 1], then [2, 3, 1, 4]. After the first full pass, the highest number is at the end. Subsequent passes sort the remaining items until the list is in order: [1, 2, 3, 4].
This method is great for small lists or as an educational tool to learn sorting algorithms. However, for large data sets, other methods might perform better due to Bubble Sort's simplicity and slower speed with large data.
The Bubble Sort algorithm is a sorting technique that continually steps through the list, compares adjoining elements, and exchanges them if they are in the wrong order. The pass through the list is continued until the list is sorted.
Below is a simple example of how Bubble Sort works, coded in Java, along with a brief explanation.
Code
public class BubbleSortExample {
void bubbleSort(int arr[]) {
int n = arr.length;
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1]) {
// swap arr[j+1] and arr[j]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
// Method to print the array
void printArray(int arr[]) {
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver method to test above
public static void main(String args[]) {
BubbleSortExample ob = new BubbleSortExample();
int arr[] = {64, 34, 25, 12, 22, 11, 90};
ob.bubbleSort(arr);
System.out.println("Sorted array");
ob.printArray(arr);
}
}
Output
After running the code, the sorted array will be printed:
Sorted array
11 12 22 25 34 64 90
Writing efficient Bubble Sort pseudocode involves outlining the algorithm in a simple, language-agnostic manner, focusing on logic rather than syntax. Here, we will cover best practices for crafting pseudocode for Bubble Sort with Python.
Pseudocode
Procedure bubbleSort(A)
n = length(A)
Repeat
swapped = false
For i = 1 to n-1 inclusive do
If A[i-1] > A[i] then
Swap(A[i-1], A[i])
swapped = true
End if
End for
n = n - 1
Until not swapped
End Procedure
Real-Life Example in Python
Now, let's translate our pseudocode into a Python program.
def bubble_sort(arr):
n = len(arr)
while True:
swapped = False
for i in range(1, n):
if arr[i-1] > arr[i]:
arr[i-1], arr[i] = arr[i], arr[i-1] # Swap elements
swapped = True
n -= 1
if not swapped:
break
# Example usage
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array:", arr)
Output
Sorted array: [11, 12, 22, 25, 34, 64, 90]
Explanation
The implementation of Bubble Sort in C or C++ involves similar logic to what we have seen with Python but adapted to the syntax and idioms of these languages. Let's look at how you can write efficient Bubble Sort code in both C and C++, including some best practices for real-world coding.
Procedure bubbleSort(A):
n = length(A)
for i from 0 to n-1:
// Track swapping
swapped = false
for j from 0 to n-i-2:
// Compare adjacent elements
if A[j] > A[j+1] then:
// Swap them
swap A[j] with A[j+1]
swapped = true
// If no two elements were swapped by inner loop, then break
if not swapped:
break
End Procedure
#include <stdio.h>
void bubbleSort(int arr[], int n) {
int i, j, temp;
int swapped;
for (i = 0; i < n-1; i++) {
swapped = 0;
for (j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
swapped = 1;
}
}
// If no two elements were swapped by inner loop, then break
if (swapped == 0)
break;
}
}
// Function to print an array
void printArray(int arr[], int size) {
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver code to test above
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
template <typename T>
void bubbleSort(vector<T>& arr) {
int n = arr.size();
bool swapped;
for (int i = 0; i < n-1; i++) {
swapped = false;
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
swap(arr[j], arr[j+1]);
swapped = true;
}
}
if (!swapped)
break;
}
}
// Function to print an array
template <typename T>
void printArray(const vector<T>& arr) {
for (const T& val : arr)
cout << val << " ";
cout << endl;
}
// Driver code to test above
int main() {
vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
cout << "Sorted array: \n";
printArray(arr);
return 0;
}
Output for Both
Sorted array:
11 12 22 25 34 64 90
Best Practices
The Bubble Sort algorithm, despite its simplicity, holds a valuable place in computer science education and introductory programming. Its simple logic—comparing and swapping adjacent elements until the entire list is in order—makes it an excellent tool for teaching the fundamentals of sorting algorithms. However, due to its quadratic time complexity, it's not the first choice for sorting large datasets.
In real-world applications, Bubble Sort finds use in scenarios where datasets are small or nearly sorted, as its performance in these cases can be surprisingly efficient. For instance, it might serve well in a classroom setting for educational purposes or in embedded systems where memory is limited and simplicity is key.
While Bubble Sort is a simple and educational tool, it is not the most efficient for large datasets. Other algorithms like QuickSort or MergeSort offer better performance with lower time complexities.
Bubble Sort is not classified as a greedy algorithm. Greedy algorithms make the optimal choice at each step to find the overall optimum. Bubble Sort follows a simple repetitive comparison and swapping process to sort elements.
It is called Bubble Sort because the sorting process lets larger values "bubble" to the end of the list or array through a series of swaps, similar to bubbles rising to the surface of water.
The "best" sorting algorithm depends on the needs of the application, including factors like dataset size, the order of input data, and memory constraints. QuickSort, MergeSort, and HeapSort are among the most efficient for large datasets.
Rohan Vats
Passionate about building large scale web apps with delightful experiences. In pursuit of transforming engineers into leaders.
Talk to our experts. We’re available 24/7.
Indian Nationals
1800 210 2020
Foreign Nationals
+918045604032
upGrad does not grant credit; credits are granted, accepted or transferred at the sole discretion of the relevant educational institution offering the diploma or degree. We advise you to enquire further regarding the suitability of this program for your academic, professional requirements and job prospects before enrolling. upGrad does not make any representations regarding the recognition or equivalence of the credits or credentials awarded, unless otherwise expressly stated. Success depends on individual qualifications, experience, and efforts in seeking employment.
upGrad does not grant credit; credits are granted, accepted or transferred at the sole discretion of the relevant educational institution offering the diploma or degree. We advise you to enquire further regarding the suitability of this program for your academic, professional requirements and job prospects before enr...