Mojo-Numerics-and-Algorithms-group / NuMojo

NuMojo is a library for numerical computing in Mojo 🔥 similar to numpy in Python.
Apache License 2.0
86 stars 15 forks source link

Add bubble sort and quick sort #44

Closed forFudan closed 2 months ago

forFudan commented 2 months ago

Add bubble sort and quick sort in numojo.core.sort module. Implement the sort method using the quick sort algorithm.

The location of the module is similar to the Numpy (numpy._core.npysort).

There is also a binary_sort function in the numojo.math.statistics.cumulative_reduce. I personally prefer a standalone sort module because the sorting functions are quite essential. Let's keep it an open discussion.

Test with an array of 10000 Float64 numbers, 1000 times.

Original array

[[      -1.2397359036589188     1.6120094337313993      1.3828016699156287      ...     -0.96682603166308989    -1.2589781838685108     -1.2540323302923684       ]]
Shape: [1, 10000]  DType: float64

==================================================
Binary sort
0.109690972 s

[[      -3.9278628912283353     -3.340264055200961      -3.2176295771029255     ...     3.9035814954840511      3.9165463112981165      4.1622896659028186        ]]
Shape: [1, 10000]  DType: float64

==================================================
Bubble sort
0.101396972 s

[[      -3.9278628912283353     -3.340264055200961      -3.2176295771029255     ...     3.9035814954840511      3.9165463112981165      4.1622896659028186        ]]
Shape: [1, 10000]  DType: float64

==================================================
Quick sort
0.00059504199999999995 s

[[      -3.9278628912283353     -3.340264055200961      -3.2176295771029255     ...     3.9035814954840511      3.9165463112981165      4.1622896659028186        ]]
Shape: [1, 10000]  DType: float64

==================================================
ndarray.sort method adopting quick sort
0.000594846 s

[[      -3.9278628912283353     -3.340264055200961      -3.2176295771029255     ...     3.9035814954840511      3.9165463112981165      4.1622896659028186        ]]
Shape: [1, 10000]  DType: float64