to write a program to implement the sorting algorithm Bubble Sort , and to analy

Question

to write a program to implement the sorting algorithmBubble Sort, and to analyze the complexity of thealgorithm.

Suppose we want to sort the elements of an array A in ascendingorder using Bubble Sort. For the following explanation,assume that the number of elements n is > 3.

·         Wefirst compare A[0] with A[1]. If A[0]>A[1] then A[0] andA[1] are swapped, otherwise no exchange happens between A[0] andA[1].

·         We nextcompare A[1] with A[2]. If A[1]>A[2] then A[1] and A[2] areswapped, otherwise no exchange happens between A[1] and A[2].

·         Wecontinue comparing in pairs and exchanging as necessary until thelast two elements of the array are compared and possibly swapped.At this point the largest element of the array will be inA[n-1].

·         Werepeat the whole process only for the first n-1 elements,not for the n elements of the array. After thissecond pass, the second largest element of the array willoccupy A[n-2].

·         Werepeat this process until the whole array is sorted.

Here is the assignment.

1.        Implement Bubble Sort in a function bSort(int A[],int n) iteratively and in a function bSortRec(int A[],int n) recursively and test each version on a small array ofintegers.

2.         Now using therand() function, generate an array of 50 random 16 bit or 32 bitintegers. Print out the array before you sort it and after you sortit. Print 5 integers per line.

3.         Do atheoretical analysis for the time your algorithm for BubbleSort takes. Count the number of comparisons bSort does tosort n values and the number of comparisons in bSortRec. Note, thealgorithm is supposed to be a quadratic algorithm, that is, thenumber of comparisons should be in O(n2).

Explanation / Answer

please rate - thanks #include #include using namespace std; voiditerative(int[],int);                   void recursive(int[],int,int&); intmain()                                { int array[50],array2[50],i,j,n=50,count=0;    srand(time(0)); for(i=0;i

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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