So we learnt various sorting algorithms, some of them are fast, like QuickSort, others, like BubbleSort have another useful property - they work "in-place" - i.e. require no additional memory, only shifting elements inside the original array.
It may seem at first glance QuickSort also can be implemented "in-place" but no - it needs constantly
to remember all "pivot" positions - both in recursive and non-recursive implementation - which means
O(log(N)) additional memory in good case and O(N) in worst case.
This time you'll need to sort array (in increasing order) using whatever algorithm you prefer, but satisfying both the following conditions:
O(N*log(N)) manner or similarin place - you are only allowed to introduce additional scalar variables and can't rely on keeping
anything in stack with recursive callsThat means we need to implement the algorithm in some specific and not very advanced language (particularly,
not having built-in sort), so it is BASIC again! The array to be sorted is A(...), its size is N.
When program finishes, it is checked that no new arrays were created.
Also it is important not to hit execution limit (on statement count).
Consider the program:
n = 15 : DIM a(n)
DATA 9, 6, 34, 14, 18, 16, 3, 31, 24, 29, 4, 21, 27, 22, 12
FOR i = 0 TO n-1 : READ a(i) : NEXT i
GOSUB sort
FOR i = 0 to n-1 : PRINT a(i);" "; : NEXT i : PRINT ""
END
sort:
FOR i = 1 TO n-1
p = i-1 : x = a(p)
FOR j = i TO n-1
IF a(j) < x THEN p = j : x = a(p)
NEXT j
a(p) = a(i-1) : a(i-1) = x
NEXT i
RETURN
It implements Selection sort in the sort subroutine. Main program just defines array a(n), fills it with
test data, calls sort and then prints result.
You can submit it as is, but the checker will say it is not fast enough - because it runs against
array of size about N=5000. So your goal is to implement some better sorting approach. Just make sure the
subroutine still is marked with sort label, other code doesn't matter.