Sorting algorithms/Cycle sort: Difference between revisions
Content deleted Content added
m =={{header|Racket}}== stub added |
→{{header|Racket}}: actual implementation added |
||
Line 842:
=={{header|Racket}}==
<lang racket>#lang racket/base
(require racket/match)
;; Sort an array in place and return the number of writes.
(define (cycle-sort! v < =?)
(define v-len (vector-length v))
(for/sum ; Loop through the array to find cycles to rotate.
((cycle-start (in-range 0 (sub1 v-len))))
(define item (vector-ref v cycle-start))
(define (find-insertion-point) ; Find where to put the item.
(+ cycle-start
(for/sum
((i (in-range (add1 cycle-start) v-len))
#:when (< (vector-ref v i) item)) 1)))
;; Put the item there or right after any duplicates
(define (insert-after-duplicates pos)
(match (vector-ref v pos)
[(== item =?) (insert-after-duplicates (add1 pos))]
[tmp (vector-set! v pos item) ; / swap
(set! item tmp) ; \ [this is my only write point]
pos]))
(define i-p (find-insertion-point))
(if (= i-p cycle-start)
0 ; If the item is already there, this is not a cycle.
(let loop ; Rotate the rest of the cycle.
((e-p (insert-after-duplicates i-p))
(W 1 #| we've already written once |#))
(if (= e-p cycle-start)
W
(loop (insert-after-duplicates (find-insertion-point))
(add1 W))))))) ; we've written again!
(module+ main
;; This will be random with duplicates
(define A (list->vector (build-list 30 (λ (i) (random 20)))))
A
(cycle-sort! A < =)
A
(define B #(1 1 1 1 1 1))
B
(cycle-sort! B < =))</lang>
{{out}}
<pre>'#(7 17 5 16 14 9 18 10 1 4 10 1 9 3 3 0 1 18 16 12 9 14 14 12 19 2 12 15 16 8)
<pre>▼
28
'#(0 1 1 1 2 3 3 4 5 7 8 9 9 9 10 10 12 12 12 14 14 14 15 16 16 16 17 18 18 19)
'#(1 1 1 1 1 1)
▲0</pre>
=={{header|REXX}}==
===version 1===
| |||