Small Basic Forum
Challenge 9 - Quick sort - Printable Version

+- Small Basic Forum (https://litdev.uk/mybb)
+-- Forum: Small Basic (https://litdev.uk/mybb/forumdisplay.php?fid=1)
+--- Forum: Challenges (https://litdev.uk/mybb/forumdisplay.php?fid=5)
+--- Thread: Challenge 9 - Quick sort (/showthread.php?tid=152)

Pages: 1 2 3 4 5 6

RE: Challenge 9 - Quick sort - AbsoluteBeginner - 10-30-2024

(translated by Google translator)

Hi all.  Shy
As I was falling asleep last night, this solution to the problem came to my mind:
Code:
'
' create a cell array
For i = 1 To 1024
  arr_cell[i] = Math.GetRandomNumber(1024)
EndFor

n_shift = 0
DisplayArray()

' put values into boxes
For i = 1 To 1024
  var_X = arr_cell[i]
  arr_box[var_X] = arr_box[var_X] + 1
EndFor

' return values ​​to cells
n_cellCursorPosition = 1

For n_boxCursorPosition = 1 To 1024
  If arr_box[n_boxCursorPosition] >= 1 Then
    For i = 1 To arr_box[n_boxCursorPosition]
      arr_cell[n_cellCursorPosition] = n_boxCursorPosition
      n_cellCursorPosition = n_cellCursorPosition + 1
    EndFor
  EndIf
EndFor

n_shift = 300
DisplayArray()
'----

'==========================================
' display the result on the screen
Sub DisplayArray
  n_size = 8
 
  GraphicsWindow.PenWidth = 1
  GraphicsWindow.PenColor = "DarkGray"
 
  For n_row = 0 To 31
    For n_column = 1 To 32
      var_X = arr_cell[n_row * 32 + n_column]
      n_green = Math.Floor(var_X / 128)
      n_red = var_X - (n_green * 128)
      GraphicsWindow.BrushColor = GraphicsWindow.GetColorFromRGB(n_red, n_green * 30, n_green * 30)
      GraphicsWindow.FillRectangle(n_column * n_size + n_shift, n_row * n_size + n_size, n_size, n_size)
    EndFor
  EndFor
EndSub

I don't know if you will be comfortable using the code if I put the code here. But, I feel sorry for wasting space on the server to release a program from the code editor.

It seems to me that it is no longer possible to sort an array faster Rolleyes . But, I haven't looked at other people's solutions yet and haven't received a solution from my Copilot.

RE: Challenge 9 - Quick sort - Scout - 10-30-2024

Hi AB,
460ms seems to be a really good time.

   

Is this the Quicksort algorithm?

RE: Challenge 9 - Quick sort - AbsoluteBeginner - 10-30-2024

(10-30-2024, 08:43 PM)Scout Wrote: Hi AB,
460ms seems to be a really good time.
...
Is this the Quicksort algorithm?

Hello, Scout.  Shy

I don't know what it's called.
I came up with it myself. And it's very fast. And the challenge is called "Quick sort".

So, everything is correct.  Angel

RE: Challenge 9 - Quick sort - litdev - 10-30-2024

Quicksort is a specific method, as shown in the Wikipedia link given by zs.

You will see significant performance improvements when the list is long > 1000s

RE: Challenge 9 - Quick sort - AbsoluteBeginner - 10-31-2024

(translated by Google Translate)

Hello everyone.

My Copilot suggested me "Quick Sort" code, which is similar to the method described in Wikipedia.
The method that I came up with, Copilot called "Sorting by baskets".
I think Copilot was wrong, because I used "boxes" in my sorting method. I don't have any "baskets" there ( that's a joke Big Grin ).

Anyway, I got a lot of pleasure from researching a topic that I was never interested in before.

And how are you?..  Wink

RE: Challenge 9 - Quick sort - Scout - 10-31-2024

AB,
your sorting method is probably a shortened version of the counting sort algorithm.
It cleverly uses the array indices.  Cool
However, it only works for integers up to the array size, in this case 1024. If there are larger numbers, not everything is sorted. Huh


   

This could be corrected if the indices are given special treatment or if the normal counting sort algorithm is used.

RE: Challenge 9 - Quick sort - AbsoluteBeginner - 11-01-2024

(10-31-2024, 09:21 PM)Scout Wrote: AB,
your sorting method is probably a shortened version of the counting sort algorithm.
It cleverly uses the array indices.
However, it only works for integers up to the array size, in this case 1024. If there are larger numbers, not everything is sorted.

This could be corrected if the indices are given special treatment or if the normal counting sort algorithm is used.

Hello, Scout.  Shy
This is an interesting version of the problem.  Rolleyes
I will again be interested in coming up with something unusual myself.

Thank you.

RE: Challenge 9 - Quick sort - AbsoluteBeginner - 11-03-2024

(translated by Google translator)

Hi all.  Shy
I think I have in my head right now the best number sorting option that can come to my mind without anyone else's help.
I'm currently converting it into real code.

I will publish this code soon. The most valuable thing about this code is that I created it myself.  Tongue

What's new with you?

RE: Challenge 9 - Quick sort - AbsoluteBeginner - 11-05-2024

(translated by Google translator)

Hi all.

I'm making slow progress on writing the code for my sorting method.
Right now, my method would probably require 9 or 10 passes to sort an array containing 1024 random numbers.
The number of passes through the array is related to the number of elements in the array by a logarithmic dependence to the base 2.

Do you think this is a good result for a sorting method created by a simple amateur who enjoys programming in Small Basic?  Blush
Or do I need to think more before publishing the code for this method of mine?
At the moment, I have read about the "Quick Sort" and "Bubble Sort" methods.
All other sorting options that came into my head were my own.  Cool

RE: Challenge 9 - Quick sort - litdev - 11-05-2024

Sorting is an extremely well researched topic and extremely unlikely any of us will discover anything new that works well.  But that isn't the point, the point is researching something, thinking about it and writing code, testing the code and comparing it with other methods objectively.  So by all means, share your variants or maybe try to write the quicksort as originally suggested.