d2jsp
d2jsp Forums > Programmer's Haven > Simple Algorithm Question
Prev12
Add Reply New Topic New Poll
carteblanche
#11 Aug 9 2018 08:19pm
Group: Member
Posts: 32,196
Joined: Jul 23 2006
Gold: 269.00
Quote (xapeu @ Aug 6 2018 09:49am)
I think that bubble sort would not be O(n) in this case.
If you had [1, 2, 3, ..., n] in your array and changed the last element to a small one like [1, 2, 3, ..., n - 1, 0] the complexity would still be O(n^2) since you would need n iterations over the n elements to move the 0 backwards 1 position at a time.

Let me know if i missed something


what if you go forwards then backwards? so 2k passes instead of just k
Cocoo
#12 Aug 10 2018 10:29am
Group: Member
Posts: 19,790
Joined: Aug 3 2011
Gold: 7,865.00
Warn: 10%
Why not a quicksort? That is what I would think to be the best in this scenario?
carteblanche
#13 Aug 10 2018 04:30pm
Group: Member
Posts: 32,196
Joined: Jul 23 2006
Gold: 269.00
Quote (Cocoo @ Aug 10 2018 12:29pm)
Why not a quicksort? That is what I would think to be the best in this scenario?


if you just happen to run across this kind of problem at work, then 100% yes use some library to just sort it. It costs the company more money for you to sit there thinking about it than to just use the library. but if it's asked in an interview, then they're looking for something different. so the focus has to be on finding a way to sort this scenario faster than O(nlogn), knowing that k << n
Go Back To Programmer's Haven Topic List
Prev12
Add Reply New Topic New Poll