Tutorial Playlist
191 Lessons1. Introduction to Java
2. What is Java?
3. History of Java
4. Java Tutorial for Beginners
5. How Do Java Programs Work?
6. JDK in Java
7. C++ Vs Java
8. Java vs. Python
9. Java vs. JavaScript
10. From Java Source Code to Executable
11. How to Install Java in Linux
12. How to Install Java in Windows 10
13. Java Hello World Program
14. Structure of Java Program and Java Syntax
15. Operators in Java
16. Java If-else
17. Switch Case In Java
18. Loops in Java
19. Infinite loop in Java
20. For Loop in Java
21. For Each Loop in Java
22. Constructor in Java
23. Constructor Overloading in Java
24. Copy Constructor in Java
25. Default Constructor in Java
26. Parameterized Constructors in Java
27. Constructor Chaining In Java
28. Finalize Method in Java
29. Static Method in Java
30. Equals Method in Java
31. Abstract Method in Java
32. toString() Method in Java
33. Difference between equals method in Java
34. Inheritance in Java
35. Multiple Inheritance in Java
36. Hierarchical Inheritance in Java
37. Java Classes and Objects
38. Scanner Class in java
39. All classes in java are inherited from which class
40. What is Nested Class in Java
41. POJO Class in Java
42. Anonymous Class in Java
43. Final Class in Java
44. Object Class in Java
45. Packages in Java
46. Access Modifiers in Java
47. Static Keyword In Java
48. Final Keyword in Java
49. Checked and Unchecked Exceptions in Java
50. User Defined Exception in Java
51. Error vs. Exception in Java
52. Java Collection
53. Collections in Java
54. Garbage Collection in Java
55. Generics In Java
56. Java Interfaces
57. Functional Interface in Java
58. Marker Interface in Java
59. Streams in Java
60. Byte stream in java
61. File Handling in Java
62. Thread in Java
63. Thread Lifecycle In Java
64. Daemon Thread in Java
65. Thread Priority in Java
66. Deadlock in Java
67. String Pool in Java
68. Java Database Connectivity(JDBC)
69. Design Patterns in Java
70. Functional Programming in Java
71. OOP vs Functional vs Procedural
72. Heap Memory and Stack Memory in Java
73. Applet in Java
74. Java Swing
75. Java Frameworks
76. Hibernate Framework
77. JUnit Testing
78. How to Install Eclipse IDE for Java?
79. Command line arguments in Java
80. Jar file in Java
81. Java Clean Code
82. OOPs Concepts in Java
83. Java OOPs Concepts
84. Overloading vs Overriding in Java
85. Java 8 features
86. String in Java
87. String to int in Java
88. Why String Is Immutable in Java?
89. Primitive Data Types in Java
90. Non-Primitive Data Types in Java
91. This and Super Keyword in Java
92. HashMap in Java
93. Comparable And Comparator in Java
94. Type Casting in Java
95. Arrays Sort in Java with Examples
96. Variable Hiding and Variable Shadowing in Java
97. Enum in Java
98. Substring in Java
99. Pattern Programs in Java
100. Hashcode in Java
101. What is ByteCode in Java?
102. How To Take Input From User in Java
103. GCD of Two Numbers in Java
104. Linked List in Java
105. Arithmetic Operators in Java
106. Conditional Operators in Java
107. Stack and Queue in Java
108. Array Length in Java
109. Number Pattern Program in Java
110. Split in java
111. Map In Java
112. Difference Between Throw and Throws in Java
113. Difference Between Data Hiding and Abstraction
114. HashSet in Java
115. String Length in Java
116. Factorial Using Recursion in Java
117. DateFormat in Java
118. StringBuilder Class in java
119. Instance variables in Java
120. Java List Size
121. Java APIs
122. Reverse an Array in Java
123. StringBuffer and StringBuilder Difference in Java
124. Java Program to Add Two Numbers
125. String to Array in Java
126. Regular Expressions in Java
127. Identifiers in Java
128. Data Structures in Java
129. Set in Java
130. Pass By Value and Call By Reference in Java
131. Try Catch in Java
132. Bubble Sort in Java
Now Reading
133. Caesar Cipher Program in Java
134. Queue in Java
135. Object Creation in Java
136. Multidimensional Array in Java
137. How to Read a File in Java
138. String Comparison in Java
139. Volatile Keyword in Java
140. Control Statements in Java
141. Jagged Array in Java
142. Two-Dimensional Array in Java
143. Java String Format
144. Replace in Java
145. charAt() in Java
146. CompareTo in Java
147. Matrix Multiplication in Java
148. Static Variable in Java
149. Event Handling in Java
150. parseInt in Java
151. Java ArrayList forEach
152. Abstraction in Java
153. String Input in Java
154. Logical Operators in Java
155. instanceof in Java
156. Math Floor in Java
157. Selection Sort Java
158. int to char in Java
159. Stringtokenizer in java
160. Implementing and Manipulating Abs in Java
161. Char array to string in java
162. Convert Double To String In Java
163. Deque in Java
164. Converting a List to an Array in Java
165. The Max function in java
166. Removing whitespace from string in java
167. String arrays in Java
168. Strings in Java Vs Strings in Cpp
169. Sum of digits of a number in Java
170. Art of Graphical User Interfaces
171. Trim in Java
172. RxJava
173. Recursion in Java
174. HashSet Java
175. Difference Between Java and Python
176. Square Root in Java
177. Reverse A String in Java
178. Even Odd Program in Java
179. Fibonacci Series in Java
180. Prime Number Program in Java
181. Java Program to Print Prime Numbers in a Given Range
182. Java Leap Year Program
183. Swapping of Two Numbers in Java
184. LCM of Two Numbers in Java
185. Math.sqrt() Function in Java
186. Area of Triangle in Java
187. Sort a String In Java
188. Factorial Program in Java
189. Javafx
190. Lambda expression in java
191. Setup Java Home and IDE on macOS
Sorting is a fundamental operation in computer science, and various algorithms are available to accomplish this task efficiently. One such algorithm is Bubble Sort, a simple yet popular sorting technique.
A comparison-based sorting algorithm known as Bubble Sort continually goes over the list compares nearby components, and, if necessary, swaps out those that are out of order. The list gets sorted completely after this step is finished. The manner that smaller entries "bubble" list gives rise to the algorithm's name. Despite being straightforward, Bubble Sort's quadratic time complexity prevents it from being a good solution for handling huge datasets. It can, however, be helpful for smaller datasets or as a teaching tool to comprehend fundamental sorting ideas.
To understand Bubble Sort better, let's look at its Java implementation. Consider an array of integers that needs to be sorted in ascending order using Bubble Sort:
javaCopy code
public class BubbleSort {
public static void bubbleSort (int[] arr) {
intn = arr.length;
fo r (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int tem p = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubble Sort(arr);
Syst em.out.println("Sorted array: ");
for (int num : arr) {
System.out.pri nt(num + " ");
}
}
}
The above code demonstrates a basic implementation of Bubble Sort in Java. The bubbleSort method takes an array arr and performs the sorting operation. The nested loops iterate through the array, comparing adjacent elements and swapping them if necessary. The sorted array is then printed using the System.out.println statement.
To comprehend the inward operations of Air Pocket Sort, we should think about a model and imagine it with a bit by bit clarification.
Model: Assume we have a variety of numbers: [5, 3, 8, 4, 2].
We will apply Bubble Sort to sort this array in ascending order.
Step 1: Starting from the beginning, compare the first two elements (5 and 3). As 5 is greater than 3, swap the elements. The array now becomes [3, 5, 8, 4, 2].
Step 2: Move to the next pair of elements (5 and 8). Since they are now properly aligned, trading is required. The array continues as before: [3, 5, 8, 4, 2].
Step 3: Continue comparing and swapping adjacent elements until the array ends. Here, the next pair is (8, 4). Swap them to obtain [3, 5, 4, 8, 2].
Step 4: Repeat the process for the remaining elements. The next pair is (8, 2), and swapping them gives [3, 5, 4, 2, 8].
Step 5: After completing one pass through the array, the largest element (8) is in its correct position at the end. Now, repeat the process for the remaining unsorted elements. The array becomes [3, 5, 4, 2, 8].
Step 6: The array is [3, 4, 2, 5, 8] after the second pass.
Step 7: The array is [3, 2, 4, 5, 8] after the third pass.
Step 8: The array is [2, 3, 4, 5, 8] after the fourth pass.
Step 9: As of now, the array is [2, 3, 4, 5, 8] following the fifth pass. At the present moment, the array is organized into rising requests.
Although the basic implementation of Bubble Sort is straightforward, it can be optimized to improve its performance. The optimization involves introducing a flag to check if any swapping occurs during a pass. If no swapping occurs, it indicates that the array is already sorted, and the algorithm can terminate early.
Here's an optimized version of Bubble Sort in Java:
javaCopy code
public static void bubbleSortOptimized(int[] arr) {
int n = arr.length;
boolean 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]) {
int temp = arr[j];
arr[j] = arr[j 1];
arr[j 1] = temp;
swapped = true;
}
}
if (!swapped) {
break;
}
}
}
In this optimized implementation, we introduce a swapped variable that keeps track of whether any swapping occurred during a pass. If no swapping occurs, the swapped variable remains false, and the algorithm breaks out of the loop, terminating early.
The worst case scenario for Bubble Sort is when the input array is in descending order. A worldly intricacy of O(n2) results from the need to contrast and trade every component and each and every component in this present circumstance, where n is the all-out number of things in the array.
Example: Consider an array [9, 8, 7, 6, 5]. Applying Bubble Sort to this array results in the following comparisons and swaps:
Pass 1: Comparisons: 4 Swaps: 4
Pass 2: Comparisons: 3 Swaps: 3
Pass 3: Comparisons: 2 Swaps: 2
Pass 4: Comparisons: 1 Swaps: 1
The total number of comparisons and swaps is given by the formula (n-1) (n-2) ... 1, which simplifies to n(n-1)/2. For an array of length 5, this results in 10 comparisons and swaps. As the array grows larger, the number of operations increases quadratically.
Bubble Sort can also be implemented using recursion. In the recursive approach, the largest element "bubbles" to the end of the array in each pass, similar to the iterative version.
Here's a recursive implementation of Bubble Sort in Java:
javaCopy code
public static void bubbleSortRecursive(int[] arr, int n) {
if (n == 1) {
return;
}
for (int i = 0; i < n - 1; i ) {
if (arr[i] > arr[i 1]) {
int temp = arr[i];
arr[i] = arr[i 1];
arr[i 1] = temp;
}
}
bubbleSortRecursive(arr, n - 1);
}
The recursive implementation takes an additional parameter, n, which represents the length of the array. The base case occurs when n becomes 1, indicating that the array is sorted. Otherwise, the algorithm performs one pass through the array, swapping adjacent elements if necessary, and recursively calls itself with n - 1.
The boundary case for Bubble Sort is when the array is already sorted. In this scenario, Bubble Sort arrays its best-case behavior, as no swapping is required during any pass. With an O(n) time complexity, where n is the number of items in the array, the algorithm will run through the array once to ensure that no swapping is required and end early.
Consider the following array: [1, 2, 3, 4, 5].
Applying Bubble Sort to this array results in the following comparisons and swaps:
Pass 1: Comparisons: 4 Swaps: 0
Pass 2: Comparisons: 3 Swaps: 0
Pass 3: Comparisons: 2 Swaps: 0
Pass 4: Comparisons: 1 Swaps: 0
The algorithm completes in a single pass, as no swapping is required, and the array is already sorted.
Yes, Bubble Sort is an in-place sorting algorithm, meaning it does not require additional memory to perform the sorting operation. The sorting is done directly on the input array, with no need for auxiliary data structures.
In the Java implementation of Bubble Sort we discussed earlier, the sorting is performed directly on the input array arr. No additional arrays or data structures are used during the sorting process.
Yes, Bubble Sort is a stable sorting algorithm. Stability refers to the ability of an algorithm to maintain the relative order of elements with equal values. In Bubble Sort, when two adjacent elements are swapped, they only change places if they are in the wrong order. Two items that share the same value will not be switched, preserving the original order.
Think of an array of items with a key-value pair as an illustration. While maintaining the relative order of items with the same key, Bubble Sort will sort the objects depending on the key.
Where is the Bubble Sort algorithm used?
Bub ble Sort, due to its simplicity, is rarely used in practice for large datasets. It can by the by being valuable in certain conditions, for example,
Bubble Sort is regularly utilized as a training instrument to represent arranging calculations as a result of how basic and clear its rationale is.
Small Datasets: Bubble Sort can be useful for sorting small datasets where efficiency is not a primary concern. Its simple implementation and in-place nature make it suitable for such scenarios.
Partially Sorted Arrays: When dealing with partially sorted arrays, Bubble Sort can have advantages over other sorting algorithms. It performs well when the array is already partially sorted or nearly sorted, as it requires fewer comparisons and swaps in such cases.
Simple implementation: Bubble Sort has a straightforward implementation, making it easy to understand and implement, especially for beginners.
In-place sorting: Bubble Sort operates directly on the input array without requiring additional memory, making it memory-efficient.
Stable sorting: Bubble Sort preserves the relative order of elements with equal values, making it a stable sorting algorithm.
Inefficient for large datasets: Bubble Sort has a time complexity of O(n^2), making it inefficient for sorting large arrays. Other sorting algorithms, such as Quick Sort or Merge Sort, offer better performance for larger datasets.
Lack of adaptability: Bubble Sort's performance does not improve based on the initial state of the array. It always performs a fixed number of passes, regardless of whether the array is already sorted or partially sorted.
In conclusion, Bubble Sort is a simple yet inefficient sorting algorithm that operates by repeatedly comparing adjacent elements and swapping them if necessary. While it has limited practical use for large datasets, it can be useful for smaller arrays or educational purposes. Understanding Bubble Sort provides a foundation for learning more advanced sorting algorithms and their optimizations.
Q1: Can Bubble Sort be used to sort strings or other data types?
A1: Yes, Bubble Sort can be used to sort strings or other data types as long as the comparison operation is defined for the data type being sorted.
Q2: How does Bubble Sort compare to other sorting algorithms?
A2: Bubble Sort has a time complexity of O(n^2), which makes it less efficient than other sorting algorithms like Quick Sort or Merge Sort. These algorithms have better average and worst-case time complexity, making them more suitable for sorting large datasets.
Q3: Can Bubble Sort be used for sorting linked lists?
A3: Bub ble Sort can be used to sort linked lists by repeatedly traversing the list and swapping adjacent nodes if necessary. However, due to the frequent swapping of nodes, Bubble Sort is not an efficient choice for sorting linked lists compared to other algorithms like Merge Sort or Insertion Sort.
Q4: Are there any real-world applications where Bubble Sort is preferred?
A4: Bubble Sort is not commonly used in real-world applications due to its inefficiency for large datasets. However, it can still be used for small datasets or scenarios where simplicity and ease of implementation outweigh the performance concerns.
PAVAN VADAPALLI
Director of Engineering
Director of Engineering @ upGrad. Motivated to leverage technology to solve problems. Seasoned leader for startups and fast moving orgs. Working …Read More
Popular
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...