Q1: The Bubblesort is another simple sorting algorithm, whose pseudocode is as f

Question

Q1: The Bubblesort is another simple sorting algorithm, whose pseudocode is as
follows:
1. Write a C++ Bubblesort(vector<T> &v) method that takes a vector v and sort the elements in this vector v using Bubble Sort scheme.
2. Your C++ program should:
• Generate 20 random numbers and stores them in a std::vector structure;
• Sorts them using the Bubblesort algorithm;

• Outputs them

3. What is the worst-case time complexity of Bubblesort algorithm? Show
how you derive the complexity.

input: a non-sorted list of n numbers, a1,a2... ,an output a list with the same numbers, sorted in non-decreasing order 1. 2. 3. for i: n to for j: toi-1 if aj > aj+1 then t--aj swap aj with aj+1 4. 4. a 5. 6. 7.

Explanation / Answer

void bubbleSort(vector<T> &v){
   T temp;
   for(int i =0; i < v.size(); i++){
       for(int j = i + 1; j < v.size(); j++){
           if(v[i] > v[j] ){
               temp = v[i];
               v[i] = v[j];
               v[j] = temp;
           }
       }
   }
}

Worst case complexity is O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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