## Introduction

Bubble Sort is most easy and least used algorithm for sorting but this is initial algorithm which comes up when we start reading about sorting. Bubble sort's running time is O(n2). This algorithm selects first 2 elements and sort them then it selects 2nd and 3rd and sort them and so on.

## Implementation

Below we have the code of bubble sort:

public class BubbleSort

{

int[] A;

public BubbleSort(int[] arr)

{

A = arr;

}

public int[] Sort()

{

for (int i = A.Length - 1; i > 0; i--)

{

for (int j = 0; j < i; j++)

{

if (A[j] > A[j + 1])

Swap(j, j + 1);

}

}

return A;

}

private void Swap(int i, int j)

{

int temp = A[i];

A[i] = A[j];

A[j] = temp;

}

}

In above code, we can see We have two loops one is inside another, actually the algorithm works like, it iterates i = (n-1) pass by outer loop and each pass will have inner loop which runs from j = 1 to i where value of i will be decreasing in each pass. In first pass, it finds the largest element in the array which will be placed to end then in second pass second largest element will be placed at second last position and so on. Given example below for better understanding.

Example: Let's suppose we have an array {3,2,6,1} to sort, then:

Pass1

3,2,6,1 => 2,3,6,1 2<3 so swaps (step1)

2,3,6,1 => 2,3,6,1 6>3 so doesn't swap (step2)

2,3,6,1 => 2,3,1,6 1<6 so swaps (step3)

Pass2

2,3,1,6 => 2,3,1,6

2,3,1,6 => 2,1,3,6

Pass3

2,1,3,6 => 1,2,3,6

Above we can see how do we make n-1 passes (n is 4 in above example) and how every pass finds largest number and place it in last indexes. For example, in pass1, step1 selects 3, 2 and finds 2 is less than 3 so swaps them, then step2 selects 3,6 but 6 is greater than 3 so doesn't swap, then in step3 it finds 1 is less than 6 so swaps them, after pass1 we find largest number 6 at end and so after pass2 we find 2nd largest number 3 at 2nd last position. Let's run above code:

BubbleSort bubbleSort = new BubbleSort(new int[] { 2, 1, 7, 4, 9, 3, 6 });

var sortedArr = bubbleSort.Sort();

foreach (int ele in sortedArr)

Console.WriteLine(ele);

Console.ReadLine();

**Output**

1

2

3

4

6

7

9

## Analysis

The algorithm behaves same as Selection Sort in terms of running time which is O(n2) . Recurrence and calculation will be same as Selection Sort, see here.

## Comments:

Nitin