Give me some suggestions to improve time complexity of this program

Question

*Bubble Sort Is Necessary

https://sololearn.com/compiler-playground/cL40WWgNlXpn/?ref=app

Answer 1

Debojit Santra Since you said Bubble Sort is mandatory, your sort() is already as good as can get on time complexity.
Bubble Sort is O(n^2) for average and worst case.

The one part where you can (and should) improve your sort() is change the start point for outer loop from i = 0 to i = front.

You use binary algorithm in search() which only works if the list is sorted.
So sort() must be run at least once.
And no enqueue() between last sort() and the search(),
Otherwise can't guarantee list is still sorted.

Finally, your list capacity will steadily shrink once rear reaches MAX_SIZE and you keep dequeueing until front also reaches MAX_SIZE.
Two solutions
👉 When rear reaches MAX_SIZE, initiate extra code to shift all list values downward so that front = 0 again, and rear goes down by how much front was decreased
👉 Implement your list as circular list. Rear would loop back to 0 when adding to list after reaching MAX. Full list now occur when rear reaches front. Adds code complexity, but not time complexity.

Answer 2

What's your desired time complexity for this program?