{"id":11449,"date":"2022-12-28T10:27:17","date_gmt":"2022-12-28T10:27:17","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=11449"},"modified":"2023-07-01T07:45:53","modified_gmt":"2023-07-01T07:45:53","slug":"bubble-sort-program-in-java","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/bubble-sort-program-in-java\/","title":{"rendered":"Bubble Sort Program in Java"},"content":{"rendered":"

\"\"<\/p>\n

In this article, we will delve into the bubble sort algorithm and its implementation in Java. We will explore the intricacies of the algorithm, examine its time and space complexity, analyze the best and worst-case scenarios, and evaluate its stability. Without further ado, let us commence with our exploration.<\/p>\n

What is Bubble Sort in Java?<\/h2>\n

Bubble Sort is an algorithm used to arrange the elements of an array or a list in either ascending or descending order. It is a comparison-based sorting algorithm, meaning that it relies on comparing the elements with each other to perform the sorting operation. You might be curious about how sorting can occur without directly comparing the elements.<\/p>\n

Alternatively, there exists a different type of sorting known as Linear sorting, which does not involve comparisons. Examples of linear sorting include Count Sort and Radix Sort. However, these methods are beyond the scope of our current discussion.<\/p>\n

In the bubble sort algorithm, during each iteration, the heaviest element "bubbles" its way to the end of the array. This implies that the first iteration identifies the maximum element, the second iteration finds the second maximum element, and so on (assuming the sorting is performed in ascending order). The steps of the bubble sort algorithm are as follows.<\/p>\n

Bubble Sort Algorithm:<\/h2>\n
    \n
  1. There will be N-1 iterations i.e. the iteration variable i varies as 0<= i < N-1. In each iteration, follow these steps:\n
      \n
    • Run a loop from 0 <= j < N-i+1. <\/li>\n
    • In this loop, compare the adjacent elements i.e. array[j] and array[j+1]. If array[j] > array[j+1], the bigger element is before the smaller one in the array. So, swap them. Else, move further.<\/li>\n<\/ul>\n<\/li>\n
    • After these N-1 iterations, the array will be sorted.<\/li>\n<\/ol>\n

      Let us demonstrate a dry run of these steps. So, consider the array shown below.<\/p>\n

      \"\"<\/p>\n

      We will now sort this array using bubble sort. So, the first iteration and its steps are shown below.<\/p>\n

      \"\"<\/p>\n

      So, in the first pass of the first iteration, we compare the first 2 elements. Since 5 is smaller than 9 i.e. the smaller element is on the left and larger on the right, the elements are in sorted positions with respect to each other. Hence, we don\u2019t swap them.<\/p>\n

      Next, we compare 9 and 8. Since 9 is greater than 8, we will swap these elements and now 8 will come before 9.<\/p>\n

      Next, 9 and 2 are compared and again 9 gets swapped with 2. Then we compare 9 and 1. Since 9 is greater than 1, we swap them. Now, we can see that the largest element of the array i.e. 9 is at its sorted position i.e. at the last of the array. This will happen in every iteration.<\/p>\n

      So, we have established a fact that in the ith iteration of bubble sort, the ith largest element will move to the ith position from the back of the array i.e. its sorted position.<\/strong><\/p>\n

      This was just the 1st iteration. Let us do one more iteration. The second iteration swaps are shown below.<\/p>\n

      \"\"<\/p>\n

      So, the box around the last element i.e. 9 shows that it is already in its sorted position and no element will be compared to 9. So, the first 2 elements i.e. 5 and 8 are compared. Since they are in sorted positions with respect to each other, no swaps take place.<\/p>\n

      Next, we compare elements 8 and 2. Since 8 is larger than 2, the swap takes place. Then, 8 and 1 are compared and since 8 is greater than 1, swapping takes place and 8 goes to the second last position of the array.<\/p>\n

      So, we got the second largest element at the second last position of the array in the second iteration of bubble sort.<\/p>\n

      This is how the complete bubble sort algorithm will continue for 4 iterations (as there are 5 elements and the number of iterations = N-1 = 5-1=4). The rest of the iterations are shown below.<\/p>\n

      \"\"<\/p>\n

      So, we can see that after 4 iterations, the array got sorted. So, now that we have understood the logic, let us write the bubble sort program in Java.<\/p>\n

      Bubble Sort Program in Java<\/strong>
      \n\t\t\t\t\t\t