What is the worst case running time for BS when given a vector of size N to sort?
Given BS in the picture.
A) What is the worst case running time for BS when given a
size N to sort?
B) Put a series of integers into this vector that would make the BS run in optimal time:
C) Put a series of integers into this vector that would make the BS run in worst case time:
![### Bubble Sort Implementation in C++
The following code demonstrates a simple implementation of the Bubble Sort algorithm in C++. The function `BS` takes a vector of integers and sorts it in ascending order.
```cpp
void BS(vector<int> & list) {
int clean_pass = false;
for (int i = 1; !clean_pass && i < list.size(); i++) {
clean_pass = true;
for(int j = 0; j < (list.size() - i); j++) {
if(list[j] > list[j+1]) { // Swap j & j+1
int temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
clean_pass = false;
}
}
}
}
```
### Explanation
- **Outer Loop**: Iterates through the list. It continues until a complete pass through the list is made without any swaps, indicating the list is sorted.
- **Inner Loop**: Compares each element with the next one. If an element is greater than the next, they are swapped to move larger elements towards the end of the list.
- **Variables**:
- `clean_pass`: A flag used to track whether the inner loop made any swaps.
- `temp`: A temporary variable used for swapping two elements.
This implementation uses an optimization to improve efficiency by stopping the sort early if a pass is made without any swaps (`clean_pass = true`). This means the list is already sorted.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Ff4f8485b-d935-478d-91e7-b806502d9702%2F0b0f07ee-aa9c-4613-8cfc-c445228b9113%2Fta3u80m_processed.png&w=3840&q=75)
From the inner for loop, it is clear that if the current element is greater than the next element of vector swap the elements, which means to sort the vectors in ascending order.
The worst case running time for any block is calculated when all the set of instructions were executed in every iteration.
Thus if block of code must execute in every iteration.
Thus, worst case running time for block BS when size of vector is N is: O(N2 ) as both the for loops executes in every iteration.
Step by step
Solved in 3 steps
