## Thursday, 29 December 2016

Bubble sort Algorithm

Bubble sort algorithm starts by comparing the first two elements of an array and swapping if necessary.

Algorithm

for i = 1:n,
swapped = false
for j = n:i+1,
if a[j] < a[j-1],
swap a[j,j-1]
swapped = true
invariant: a[1..i] in final position
break if not swapped
end

Bubble Sorting Code Using C# Language
class Lab
{
static void Main(string[] args)
{
int[] ArrayNumber = { 88, 75, 44, 91, 66, 11, 98 };
int temp;
int ArraynumLength = ArrayNumber.Length;
//sorting an array
for (int i = 1; (i <= (ArraynumLength - 1)); i++)
{
for (int j = 0; j < (ArraynumLength - 1); j++)
{
if (ArrayNumber[j + 1] > ArrayNumber[j])
{
temp = ArrayNumber[j];
ArrayNumber[j] = ArrayNumber[j + 1];
ArrayNumber[j + 1] = temp;

}
}
}
//Sorted array
foreach (int num in ArrayNumber)
{
Console.Write("\t {0}", num);
}
}
}

Complexity Analysis of Bubble Sorting

In Bubble Sort, n-1 comparisons will be done in 1st pass, n-2 in 2nd pass, n-3 in 3rd pass and so on. So the total number of comparisons will be

(n-1)+(n-2)+(n-3)+.....+3+2+1
Sum = n(n-1)/2
i.e O(n2)

Hence the complexity of Bubble Sort is O(n2).