Seriously? Creating some order in the chaos!
There are many sorting algorithms that have been created in the past and there will be variants of those to be useful in the future.
The plan is to show some of those here.
Bubblesort, Heapsort, Quicksort to name a few.
For starters I needed to sort an imported array of 1000 integers. All these integers had 5 digits. So the most suitable sort algorithm was Radix sort. Radix sort needs a bucket for each possible digit in the number system used. So in the decimal number sy stem you need 10 buckets. The idea is you sort your input from the last digit to the first digit each time into the buckets.
Because Meta does not really supports dynamic extending of arrays I faced a creative challenge again. I ended up only needing 1 extra array of the length of the original input.
Five digits meant that a NATURAL16! was not large enough and thus a NATURAL32! type was chosen, and hence the binary array had to become 4000 long to hold the 1000 integers.
I was not in the mood to do much fiddling with indexes, constantly subttracting 1, so I decided to grow the array by 1 element. This way the indexing matched the element in the array.
One could choose to put the last element in the slot with index 0 if you consider the extra memory space problematic.
So the input is a list of 1000 of those integers:
22222
12637
...
...
90823
83544
And this is the algorithm I came up with
Meta [
file: radix-sort-example.meta
]
let [array array-sort] binary! 4004
change/repeat array 0 4004
change/repeat array-sort 0 4004
file: "input-task1.txt"
dir: "./"
infile: to file! join/with dir file
Either file-handle= try OPEN infile [
write/line "Reading data.."
][
write/line "Not able to open input file"
bye
]
array-index: 1
while not is-tail file-handle [
inline: take/line file-handle
number-in: to natural32! copy cut inline 5
unportable change/binary skip array array-index * size-of natural32! number-in
increment array-index
]
write/line "Data read. Processing.."
close file-handle
factor: 10
sort-index: 1
for position 5 [
base: power factor (position - 1)
for radix [0 9] [
for i 1000 [
number: as natural32! skip array i * size-of natural32!
if radix = remainder to natural! (number / base) 10 [
unportable change/binary skip array-sort sort-index * size-of natural32! number
increment sort-index
]
]
]
for tel 4004 [
poke array tel pick array-sort tel
]
sort-index: 1
]
write "Number 1 at start " write/line as natural32! skip array 1 * size-of natural32!
write "Number 1000 at end " write/line as natural32! skip array 1000 * size-of natural32!
And much to my own surprise ,just kidding the array was sorted.