Rosetta Code

Sorting algorithms/Quicksort: Difference between revisions

Page Discussion

Sorting algorithms/Quicksort (view source)

Revision as of 23:04, 25 March 2024

2,130 bytes removed ,  1 month ago
→‎{{header|Bruijn}}
(→‎{{header|zig}}: new version based on Rust, with generic comparator function, annotate versions)
(10 intermediate revisions by 8 users not shown)
Line 2,887:
(quick,sober)
(quick,sort)</pre>
 
=={{header|Bruijn}}==
<syntaxhighlight lang="bruijn">
:import std/Combinator .
:import std/Number .
:import std/List .
 
sort y [[0 [[[case-sort]]] case-end]]
case-sort (4 lesser) ++ (2 : (4 greater))
lesser (\lt? 2) <#> 1
greater (\ge? 2) <#> 1
case-end empty
 
:test (sort ((+3) : ((+2) : {}(+1)))) ((+1) : ((+2) : {}(+3)))
</syntaxhighlight>
 
=={{header|C}}==
Line 4,376 ⟶ 4,391:
 
=={{header|Elena}}==
ELENA 56.0x :
<syntaxhighlight lang="elena">import extensions;
import system'routines;
Line 4,393 ⟶ 4,408:
auto more := new ArrayList();
self.forEach::(item)
{
if (item < pivot)
Line 4,676 ⟶ 4,691:
=={{header|Fortran}}==
{{Works with|Fortran|90 and later}}
<syntaxhighlight lang="fortran">
 
recursive subroutine fsort(a)
'''WARNING: The implementation of QuickSort in Fortran below is flawed:'''
use inserts, only:insertion_sort !Not included in this posting
# If the largest element is in the last slot, the call to QSort(A(marker:),nA-marker+1) goes beyond the end of the array. This can cause exceptions and bad results.
implicit none
# The use of a random number causes non reproducible performance.
!
 
! PARAMETER definitions
'''Instead of this algorithm rather use https://gist.github.com/t-nissie/479f0f16966925fa29ea'''
!
 
integer, parameter :: changesize = 64
<syntaxhighlight lang="fortran">MODULE qsort_mod
!
 
! Dummy arguments
IMPLICIT NONE
!
 
real, dimension(:) ,contiguous :: a
TYPE group
intent (inout) a
INTEGER :: order ! original order of unsorted data
!
REAL :: VALUE ! values to be sorted by
! Local variables
END TYPE group
!
 
integer :: first = 1
CONTAINS
integer :: i
 
integer :: j
RECURSIVE SUBROUTINE QSort(a,na)
integer :: last
 
! DUMMY ARGUMENTSlogical :: stay
INTEGER, INTENT(in) real :: nA t
TYPE (group), DIMENSION(nA),real INTENT(in out) :: A x
!
 
!*Code
! LOCAL VARIABLES
!
INTEGER :: left, right
REAL :: randomlast = size(a, 1)
if( (last - first)<changesize )then
REAL :: pivot
call insertion_sort(a(first:last))
TYPE (group) :: temp
INTEGER :: marker return
end if
 
IF j = shiftr(nA(first >+ last), 1) THEN+ 1
!
 
x CALL= random_NUMBERa(randomj)
i = first
pivot = A(INT(random*REAL(nA-1))+1)%VALUE ! Choice a random pivot (not best performance, but avoids worst-case)
leftj = 1last
rightstay = nA.true.
do !while Partition( loopstay )
DO do while ( a(i)<x )
IF (left > i = right)i + EXIT1
DOend do
do while ( IF x<a(A(rightj)%VALUE <= pivot) EXIT
right j = rightj - 1
ENDend DOdo
DOif( j<i )then
IF (A(left)%VALUEstay >= pivot) EXIT.false.
left = left + 1else
END DO t = a(i) ! Swap the values
IF (left < right a(i) THEN= a(j)
temp = Aa(leftj) = t
A(left) i = Ai + 1 ! Adjust the pointers (rightPIVOT POINTS)
A(right) j = tempj - 1
ENDend IFif
end END DOdo
if( first<i - 1 )call fsort(a(first:i - 1)) ! We still have some left to do on the lower
 
if( j + 1<last )call fsort(a(j + 1:last)) ! We still have some left to do on the upper
IF (left == right) THEN
marker = left + 1return
end ELSEsubroutine fsort
</syntaxhighlight>
marker = left
END IF
 
CALL QSort(A(:marker-1),marker-1)
CALL QSort(A(marker:),nA-marker+1) WARNING CAN GO BEYOND END OF ARRAY DO NOT USE THIS IMPLEMENTATION
 
END IF
 
END SUBROUTINE QSort
 
END MODULE qsort_mod
! Test Qsort Module
PROGRAM qsort_test
USE qsort_mod
IMPLICIT NONE
 
INTEGER, PARAMETER :: nl = 10, nc = 5, l = nc*nl, ns=33
TYPE (group), DIMENSION(l) :: A
INTEGER, DIMENSION(ns) :: seed
INTEGER :: i
REAL :: random
CHARACTER(LEN=80) :: fmt1, fmt2
! Using the Fibonacci sequence to initialize seed:
seed(1) = 1 ; seed(2) = 1
DO i = 3,ns
seed(i) = seed(i-1)+seed(i-2)
END DO
! Formats of the outputs
WRITE(fmt1,'(A,I2,A)') '(', nc, '(I5,2X,F6.2))'
WRITE(fmt2,'(A,I2,A)') '(3x', nc, '("Ord. Num.",3x))'
PRINT *, "Unsorted Values:"
PRINT fmt2,
CALL random_SEED(put = seed)
DO i = 1, l
CALL random_NUMBER(random)
A(i)%VALUE = NINT(1000*random)/10.0
A(i)%order = i
IF (MOD(i,nc) == 0) WRITE (*,fmt1) A(i-nc+1:i)
END DO
PRINT *
CALL QSort(A,l)
PRINT *, "Sorted Values:"
PRINT fmt2,
DO i = nc, l, nc
IF (MOD(i,nc) == 0) WRITE (*,fmt1) A(i-nc+1:i)
END DO
STOP
END PROGRAM qsort_test</syntaxhighlight>
{{out}}
<pre>
Compiled with GNU Fortran 9.3.0
Unsorted Values:
Ord. Num. Ord. Num. Ord. Num. Ord. Num. Ord. Num.
1 47.10 2 11.70 3 35.80 4 35.20 5 55.30
6 74.60 7 28.40 8 30.10 9 70.60 10 66.90
11 15.90 12 71.70 13 49.80 14 2.60 15 12.80
16 93.00 17 45.20 18 21.50 19 20.70 20 39.50
21 9.20 22 21.60 23 18.60 24 22.80 25 98.50
26 97.50 27 43.90 28 8.30 29 84.10 30 88.80
31 10.30 32 30.50 33 79.30 34 24.40 35 45.00
36 48.30 37 69.80 38 86.00 39 68.40 40 22.90
41 7.50 42 18.50 43 80.40 44 29.60 45 43.60
46 11.20 47 36.20 48 23.20 49 45.30 50 12.30
 
Sorted Values:
Ord. Num. Ord. Num. Ord. Num. Ord. Num. Ord. Num.
14 2.60 41 7.50 28 8.30 21 9.20 31 10.30
46 11.20 2 11.70 50 12.30 15 12.80 11 15.90
42 18.50 23 18.60 19 20.70 18 21.50 22 21.60
24 22.80 40 22.90 48 23.20 34 24.40 7 28.40
44 29.60 8 30.10 32 30.50 4 35.20 3 35.80
47 36.20 20 39.50 45 43.60 27 43.90 35 45.00
17 45.20 49 45.30 1 47.10 36 48.30 13 49.80
5 55.30 10 66.90 39 68.40 37 69.80 9 70.60
12 71.70 6 74.60 33 79.30 43 80.40 29 84.10
38 86.00 30 88.80 16 93.00 26 97.50 25 98.50
</pre>
A discussion about Quicksort pivot options, free source code for an optimized quicksort using insertion sort as a finisher, and an OpenMP multi-threaded quicksort is found at [http://balfortran.org balfortran.org]
 
=={{header|FreeBASIC}}==
Line 8,089 ⟶ 8,026:
 
=={{header|Python}}==
<syntaxhighlight lang="python">def quickSortquick_sort(arrsequence):
lesslesser = []
pivotListequal = []
moregreater = []
if len(arrsequence) <= 1:
return arrsequence
pivot = sequence[0]
else:
for element in pivot = arr[0]sequence:
forif ielement in< arrpivot:
if i < pivot:lesser.append(element)
elif element > less.append(i)pivot:
elif i > pivot:greater.append(element)
more.append(i)else:
else:equal.append(element)
lesser = quick_sort(lesser)
pivotList.append(i)
lessgreater = quickSortquick_sort(lessgreater)
return lesser + equal + greater
more = quickSort(more)
 
return less + pivotList + more
 
a = [4, 65, 2, -31, 0, 99, 83, 782, 1]
a = quick_sort(a)
a = quickSort(a)</syntaxhighlight>
</syntaxhighlight>
 
In a Haskell fashion --
Line 8,787 ⟶ 8,725:
return</syntaxhighlight>
 
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
, 7 6 5 9 8 4 3 1 2 0: e.Arr
= <Prout e.Arr>
<Prout <Sort e.Arr>>;
};
 
Sort {
= ;
s.N = s.N;
s.Pivot e.X =
<Sort <Filter s.Pivot '-' e.X>>
<Filter s.Pivot '=' e.X>
s.Pivot
<Sort <Filter s.Pivot '+' e.X>>;
};
 
Filter {
s.N s.Comp = ;
s.N s.Comp s.I e.List, <Compare s.I s.N>: {
s.Comp = s.I <Filter s.N s.Comp e.List>;
s.X = <Filter s.N s.Comp e.List>;
};
};</syntaxhighlight>
{{out}}
<pre>7 6 5 9 8 4 3 1 2 0
0 1 2 3 4 5 6 7 8 9</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
Line 9,586 ⟶ 9,551:
def last: $(2);
def pivot: $@quicksort($first);
[@: $first(1) + 1, $last ] -> #;
$(2) -> #
 
when <?($(2) <..~$(1)>)@> do
def limit: $(2);
@quicksort($first): $@quicksort($limit);
@quicksort($limit): $pivot;
Line 9,595 ⟶ 9,561:
[ $limit + 1, $last ] !
 
when <?($@quicksort($(2)) <$pivot~..>)> do
[ $(1), $(2) - 1] -> #
 
when <?($@quicksort($(1)@) <..$pivot>)> do
[@: $(1)@ + 1,; $(2)] -> #
 
otherwise
def temp: $@quicksort($(1)@);
@quicksort($(1)@): $@quicksort($(2));
@quicksort($(2)): $temp;
[@: $(1)@ + 1,; $(2) - 1] -> #
end partial
@: $;
Line 10,076 ⟶ 10,042:
=={{header|Wren}}==
{{libheader|Wren-sort}}
<syntaxhighlight lang="ecmascriptwren">import "./sort" for Sort
 
var asarray = [
[4, 65, 2, -31, 0, 99, 2, 83, 782, 1],
[7, 5, 2, 6, 1, 4, 2, 6, 3],
["echo", "lima", "charlie", "whiskey", "golf", "papa", "alfa", "india", "foxtrot", "kilo"]
]
for (a in asarray) {
System.print("Before: %(a)")
Sort.quick(a)
Marvin
55

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/348469...362943"