Array Sort

[John]

We haven't had a code challenge in a while so I thought I would suggest an Array Sort challenge in your language of choice.

I gave this a try in native ScriptBasic but I would love to extend the T module with it done in C. The speed of SPLITA gives me hope array access at the C level would be much faster.

ScriptBasic Initial Submission

[AIR]

Code: Go

1. package main
2.  
3. import (
4.     "fmt"
5.     "sort"
6.     "strings"
7. )
8.  
9. func main() {
10.     s := strings.Split("pear,cranberry,orange,apple,carrot,banana,grape", ",")
11.     sort.Strings(s)
12.     fmt.Println(strings.Join(s, "\n"))
13. }

[riveraa@mini ~/Projects/go/sort] $ time ./sort
apple
banana
carrot
cranberry
grape
orange
pear

real    0m0.006s
user    0m0.002s
sys    0m0.002s

[John]

Nice to see GO has native array sort. I was hoping for something in C I could use in an extension module.

Based on your fast PC compared to my PoS PC, SB seems faster than GO. Try the bible line sort in GO.

[AIR]

This was done on my Mac Mini:

      Model Name: Mac mini
      Model Identifier: Macmini6,2
      Processor Name: Intel Core i7
      Processor Speed: 2.3 GHz
      Number of Processors: 1
      Total Number of Cores: 4

[John]

That's twice as fast as my PC running at 1.3 ghz 4 cores.

[jalih]

8th version using builtin Timsort to sort bible text lines and output some sorted lines:

Code: [Select]

"bible.txt" f:slurp >s "\n" s:/ var, lines


: app:main
  lines @ ' s:cmp a:sort
  a:len n:1- >r ( a:@ . cr ) r@ 10 n:- r> loop drop
  bye ;

Output is:

Code: [Select]

PS C:\temp> 8th .\sort.8th
Zebulun and Naphtali were a people that jeoparded their lives unto the death in the high places of the field.
Zebulun shall dwell at the haven of the sea; and he shall be for an haven of ships; and his border shall be unto Zidon.
Zedekiah was one and twenty years old when he began to reign, and he reigned eleven years in Jerusalem. And his mother's name was Hamutal the daughter of Jeremiah of Libnah.
Zedekiah was one and twenty years old when he began to reign, and reigned eleven years in Jerusalem.
Zelek the Ammonite, Naharai the Berothite, the armourbearer of Joab the son of Zeruiah,
Zelek the Ammonite, Nahari the Beerothite, armourbearer to Joab the son of Zeruiah,
Zenan, and Hadashah, and Migdalgad,
Zion heard, and was glad; and the daughters of Judah rejoiced because of thy judgments, O LORD.
Zion shall be redeemed with judgment, and her converts with righteousness.
Zion spreadeth forth her hands, and there is none to comfort her: the LORD hath commanded concerning Jacob, that his adversaries should be round about him: Jerusalem is as a menstruous woman among them.
Ziph, and Telem, and Bealoth,
PS C:\temp>

Timing is:

Code: [Select]

PS C:\temp> Measure-Command { 8th .\sort.8th }


Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 0
Milliseconds      : 320
Ticks             : 3203650
TotalDays         : 3,70792824074074E-06
TotalHours        : 8,89902777777778E-05
TotalMinutes      : 0,00533941666666667
TotalSeconds      : 0,320365
TotalMilliseconds : 320,365


[John]

Wow!

If 8th wasn't so cryptic to learn I would give it a try.

I'm still hoping for a submission that doen't have SORT as a native function. The SB version was based on bubble sort code I found.

[AIR]

C stdlib has these available: heapsort, heapsort_b, mergesort, mergesort_b, qsort, qsort_b, qsort_r

Using qsort:

Code: C

1. #include <stdlib.h>
2. #include <stdio.h>
3. #include <strings.h>
4.  
5. int string_cmp(const void *a, const void *b) {
6.     const char **p_a = (const char **)a;
7.     const char **p_b = (const char **)b;
8.     return strcmp(*p_a, *p_b);
9. }
10.  
11. int main (int argc, char **argv) {
12.     char *s[] = {"pear","cranberry","orange","apple","carrot","banana","grape"};
13.     size_t s_len = sizeof(s) / sizeof(char *);
14.     qsort(s, s_len, sizeof(char *), string_cmp);
15.     for (size_t i = 0; i < s_len; i++) {
16.         printf("%s\n", s[i]);
17.     }
18.     return 0;
19. }

[riveraa@mini ~/Projects/C/Sort] $ time ./Sort
apple
banana
carrot
cranberry
grape
orange
pear

real    0m0.004s
user    0m0.001s
sys    0m0.001s

SB submission:

[riveraa@mini ~/sb] $ time ./AppRun sort.sb
apple
banana
carrot
cranberry
grape
orange
pear

real    0m0.044s
user    0m0.020s
sys    0m0.014s

[John]

Thanks AIR!

That is what I was hoping for. Does these SORT C functions allow me to use something other than a C character array? I'm looking for a function that would do the heavy lifting but let me deal with access to the array.

Actually SB does pretty good compared to a compiled C program. I bet a 1/3 of that time could be reduced not using AppImage. (time AppImage running a SB script with just a remark statement)

[AIR]

If you mean can you use numbers, you would need to used a different comparison function.  If you mean can you use SB strings, the module interface provides conversion features so you essentially are using character arrays within a given module.

AppRun is not an appimage (which don't run on MacOS).  It's a bash script.
I don't permanently configure SB on any of my systems.  I use the script to set up a temporary environment that is wiped when the script is done.  I do this to avoid some of the issues you've encountered with multiple installed version of SB conflicting.

[John]

I want to use SB arrays in the extension module but find a sort routine that would allow me to create, read and write SB arrays. I need control at each iteration.

It's starting to look like the minimal performance increase doing it in an extension module isn't worth the effort for as much as I use array sort.

[John]

Here is a Quicksort in Elk Scheme.

Code: Scheme

1. ;;; -*-Scheme-*-
2. ;;;
3. ;;; Quicksort (straight from Wirth, Algorithmen & Datenstrukturen, p. 117)
4.  
5. (provide 'sort)
6.  
7. (define (sort obj pred)
8.   (if (vector? obj)
9.       (sort! (vector-copy obj) pred)
10.       (vector->list (sort! (list->vector obj) pred))))
11.  
12. (define (sort! v pred)
13.   (define (internal-sort l r)
14.     (let ((i l) (j r) (x (vector-ref v (quotient (1- (+ l r)) 2))))
15.       (let loop ()
16.         (do () ((not (pred (vector-ref v i) x))) (set! i (1+ i)))
17.         (do () ((not (pred x (vector-ref v j)))) (set! j (1- j)))
18.         (if (<= i j)
19.             (begin
20.               (vector-set! v j (vector-set! v i (vector-ref v j)))
21.               (set! i (1+ i))
22.               (set! j (1- j))))
23.         (if (<= i j)
24.             (loop)))
25.       (if (< l j)
26.           (internal-sort l j))
27.       (if (< i r)
28.           (internal-sort i r))))
29.   (let ((len (vector-length v)))
30.     (if (> len 1)
31.         (internal-sort 0 (1- len)))
32.     v))
33.  

[AIR]

Using ZShell:

Code: Bash

1. #!/usr/bin/env zsh
2.  
3. s=(pear cranberry orange apple carrot banana grape)
4. printf '%s\n' "${(o)s[@]}"
5.  

[riveraa@mini ~/tmp] $ time ./sort.sh
apple
banana
carrot
cranberry
grape
orange
pear

real    0m0.010s
user    0m0.004s
sys    0m0.003s

[John]

Very cool!

I never heard of ZShell before.