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); } Console.Read(); } }
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).
No comments:
Post a Comment
Note: only a member of this blog may post a comment.