Problem 325 Ultimate Sort Trial
Back to General discussions forum
Hi Everyone!
May I ask someone to check my code? On clicking "Run it" button it works as it should, sorts the array in-place and is fast enough. But after trying to submit my solution the checker always says that "Error: Runtime error (line #31): Execution limit reached: 1500000 statements"
And the field "Your input data: " contains a single value which is 1.
I think that the handling of the input parameters may caues this.
I've tried reading the input with DATA and READ (as it is in the example) and I've also tried with INPUT command. None of them made it pass. I have tested it with the case n=1 (my sorting algorithm just returns without doing anything)
I feel a little confused...
I think it would be enough help to know what the main program should be. The problem statement only contains the requirement that the name of the subroutine should be "sort". I do not know what code would be injected around my solution (how to prepare my submission to handle input data)
Hi Friend!
Sorry for confusion, but you don't need reading input in this program (yourself).
You only need to implement the sorting part.
When you submit it, your code is modified (real data reading code is prepended before or something like this, I don't
remember exactly), so the array is created for you and filled with values. Then it does gosub sort so that lines
with n=15 etc are skipped.
So your code works on server with different data (and larger in amount) than what you execute with "Run It". Most simple sorting algorithms won't work due to array size (it is what is happening - your code needs to be faster).
what the main program should be.
it should not be :)
e.g. only sort function is what you need to write. "main" program is added automatically before running it on server.
Yes, I tried it previously but the error still came. Then I started to investigate it and realized that although the implementation of optimized bubble sort (based on wiki pseudo-code) is O(n*logn) regarding the number of comparisons but the checker gives error because of exceeding the number of statements! :) Swapping of two adjecent elements costs 3 statements...that's the problem. So I need a better implmentation (or even a better sorting algorithm)
Anyway, thank you for the quick response :)
optimized bubble sort (based on wiki pseudo-code) is O(n*logn) regarding the number of comparisons
I'm curious :) I can't find where or how it is said to be O(n*logn)... I'm not very well acquainted with this
optimization, but given that bubble sort is the the worst of all quadratic algorithms I suspect such optimization
won't win much. And yep, with 5000 numbers we may expect over 10 mln comparisons only, not mentioning that
other operations also count...
You can generate say about 100, 300, 1000 random numbers yourself and see at which size your algorithm breaks the execution limit. That may give some insight. Honestly I don't think any quadratic algorithm may fit.
Ok, problem is done successfully :) (which made me Sensei, haha :) ) I found a suitable sorting method for this problem. Thanks for your support!
Congrats - with problem, with new rank - and by the way, for being the top of ranking list for your nice and curious country :)
Thank you very much, I love this site and thanks your kind words about my country. :) This site gives proof of that any nationalities can be together and collaborate despite of the political situation of our times. I like this community, it is a good feeling to be part of it.