Implementation and Analysis of Bubble Sort

Implementation of Bubble Sort with C# and analysis of running time


Category: Data Structure And Algorithms Tags: C#, Java, C++ Programming

Bubble Sort Code Files

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.


Like 1 Person
Last modified on 29 October 2018
Nikhil Joshi

Nikhil Joshi
Ceo & Founder at Dotnetlovers
Atricles: 132
Questions: 9
Given Best Solutions: 9 *

Comments:

Nitin
Remember the time when I started data structure!!
Like 1 Person on 29 March 2016

You are not loggedin, please login or signup to add comments:

Existing User

Login via:

New User



x