DAA: Bubble Sort Algorithm
Bubble Sort Algorithm
The bubble sort algorithm is also known as the sinking algorithm. In this algorithm, we iterate over the array, and it takes two adjacent elements and swaps them if they are in the wrong order (ascending or descending). The step is continued until the whole array is sorted in a particular manner (ascending or descending).
Though the algorithm works poorly in real-world tools, due to its simplicity bubble sort algorithm is introduced as a primary tool when the algorithm concept is started. This algorithm takes a lot of time when the number of exchanges is more.
After each pass, the highest element is pushed to the last position. Similarly, the process is followed to push the second-highest number to the second last position and so on.
The first loop runs for (N-1) iterations. The second pass loop will run for (N-2) positions and so on.
Time complexity
Worst case: O(n^2)
Best case: O(n)
Average case: O(n^2)
Space complexity: O(1)
Example - let arr[] = {14, 33, 27, 35, 10} and n = 5
Pass 1
14 < 33 No swap takes place
Takes 33 and 27
Compares 27 < 23
After swap array becomes
Takes 33 and 35 compares to 33 < 35; no swap happens
Takes 35 and 10 compares 10 < 35
Swaps 10 and 35
After pass 1, 35 has reached its original place in the array that is the last index.
Pass 2
33 comes to its original place i.e, index 4.
Pass 3
Pass 4
C++ code:
#include <bits/stdc++.h>
using namespace std;
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
// A function to implement bubble sort algorithm
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++) // Outer loop for comparing the ith element
{
for (j = 0; j < n-i-1; j++) // Inner loop for comparing the ith element with other elements
{
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}
}
}
/* Function to print an sorted array */
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++) // Iterate through the array
cout << arr[i] << " ";
cout << endl;
}
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
cout<<"Sorted array: \n";
printArray(arr, n);
return 0;
}
C code:
#include <stdio.h>
// Swap function swaps two numbers
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
// A function to implement bubble sort algorithm
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++) // Outer loop for comparing the ith element
{
for (j = 0; j < n-i-1; j++) // Inner loop for comparing the ith element with other elements
{
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}
}
}
/* 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");
}
// Main function to call bubble sort and print
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90}; // The array to be sorted
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Java code:
class BubbleSortAlgorithm
{
void bubbleSort(int arr[])
{
int n = arr.length;
for (int i = 0; i < n-1; i++) // Outer loop for comparing ith element
for (int j = 0; j < n-i-1; j++) // inner loop for comparing ith element with all other elements
if (arr[j] > arr[j+1])
{
// swap if greater i.e, arr[j+1] and arr[j]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
/* Prints 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();
}
// Main function to call bubble sort and print function
public static void main(String args[])
{
BubbleSort ob = new BubbleSort();
int arr[] = {64, 34, 25, 12, 22, 11, 90};
ob.bubbleSort(arr);
System.out.println("Sorted array");
ob.printArray(arr);
}
}