Bubble sort

• The bubble sort works by comparing each item in the list with the item next to it and swapping them if required 
• The algorithm repeats this process until it makes a pass all the way through the list without swapping any items (in other words, all items are in the correct order) 
• This causes larger values to ‘bubble’ to the end of the list while smallervalues ‘sink’ towards the beginning of the list 
• In brief, the bubble sort derives its name from the fact that the smallest data item bubbles up to the topof the sorted array

Bubble sort complexity

The time complexity of bubble sort in the best case, average case, and worst case. 
1. Time Complexity

  

Case	Time Complexity
a]Best Case	O(n)
b]Average Case	O(n2)
c]Worst Case	O(n2)

Best Case Complexity - It occurs when there is no sorting required, i.e. the array is already sorted. The best-case time complexity of bubble sort is O(n).

 
Average Case Complexity - It occurs when the array elements are in jumbled order that is not properly ascending and not properly descending. The average case time complexity of bubble sort is O(n2).

 
Worst Case Complexity - It occurs when the array elements are required to be sorted in reverse order. That means suppose you have to sort the array elements in ascending order, but its elements are in descending order. The worst-case time complexity of bubble sort is O(n2).


The Space Complexity of Bubble Sort
2. Space Complexity

a]Space Complexity                        O(1)

b]Stable                                            YES


The space complexity of bubble sort is O(1). It is because, in bubble sort, an extra variable is required for swapping.

The space complexity of optimized bubble sort is O(2). It is because two extra variables are required in optimized bubble sort.

**C++ code for implement Bubble Sorting Algorithm

#include<iostream.h>	
#include<conio.h>	

using namespace std;

void swap(int *xp, int *yp)

{

int temp = *xp;

*xp = *yp;

*yp = temp;

}



// function to implement bubble sort

void bubbleSort(int arr[], int n)

{

int i, j;

for (i = 0; i < n-1; i++)

// Last i elements are already in place

for (j = 0; j < n-i-1; j++)

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++)

cout << arr[i] << " ";

cout << endl;

}

// Driver code

void main()

{

int arr[] = {121,11,152,65,30,150,20};

int n = sizeof(arr)/sizeof(arr[0]);

clrscr();

bubbleSort(arr, n);

cout<<"Sorted array using Bubble Sort: \n";

printArray(arr, n);

//return 0;

getch();

}

OUTPUT:-