Question 1: Let's say we have bubble sort algorithm which sorts numbers in ascending order. Intuitively one might agree that the worst case input for this algorithm is array already sorted in descending order. Like I said intuitively one might agree, but I am looking for a proof or formal argument why in such case, array already sorder in descending order is the worst case (and why not other arrangement of elements is worse than that worse case).

Also, aside, if you can comment on my below proof which computes worst case complexity of bubble sort WITHOUT the question 1, I would also appreciate.

In other words i would appreciate: (a) answer on question1, and (b) if my proof below (which doesn't rely on question 1) is correct.

PROOF(might not be written down in best way but hope you get the idea):

Let A[i] be element in array, such that it is x[j]-th biggest where x=[0,1,2...,arraySize] (e.g. , in array [10,1,22,3,4] 10 is 4th biggest, where x = [0,1,2,3,4]).

By definition in bubble sort, if I compare ALL elements with A[i], it will lose at most x[j]-1 times (e.g. 10 will lose with with 1,3,4 because it was 4th biggest) with other elements - or in other words I will need x[j]-1 swaps.

It follows that for each A[i] it can be swapped at most x[j] times.

Which gives 0+1+2+..+j = j*(j+1)/2.

  • $\begingroup$ Your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. $\endgroup$ – David Richerby Jan 29 '18 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.