choice. eys is called 25. Another way to sort adjacent records exchanges those f

Question

choice. eys is called 25. Another way to sort adjacent records exchanges those fo sort. Bubble Sort scans to have keys. After the first time through list, ound with the largest key the smallest key) is moved the to its proper position This process is done repeatedly on the remaining, unsorted part of th list until the list is completely sorted Write the Bubble Sort algorithm Anal and show the results using order notation. Compare the pe formance of the Bubble Sort algorithm to those of Insertion Sort Exchange Sort, and Selection Sort.

Explanation / Answer

Algorithm BubbleSort(list A, n)
Inputs: A (list to be sorted), n (size of A)
Output: A in sorted order

Start
do
   tmp = 0;
   for i = 1 to n-1 do
       if (A[i-1] > A[i])
           swap A[i-1], A[i];
           tmp = i;
       end if
   end for
   n = tmp;
while (n != 0)
end

Best case: No swap occurs and time complexity is O(n)
Worst case: Array is in descending order.
Number of comparisons = (n-1) + (n-2) + ....... 1 = n(n-1) / 2 = O(n^2)

The worst case running time of bubble sort, insertion and selection sort is same. Bubble sort performs better than selection sort in best case since selection sort takes O(n^2) time in best case also. Bubble and insertion sort both take O(n) time in best case.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.