Sorting algorithms/Comb sort: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
Line 346: | Line 346: | ||
} |
} |
||
} |
} |
||
}</lang> |
|||
=={{header|C++}}== |
|||
This is copied from [[wp:Comb sort|the Wikipedia article]]. |
|||
<lang cpp>template<class ForwardIterator> |
|||
void combsort ( ForwardIterator first, ForwardIterator last ) |
|||
{ |
|||
static const double shrink_factor = 1.247330950103979; |
|||
typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type; |
|||
difference_type gap = std::distance(first, last); |
|||
bool swaps = true; |
|||
while ( (gap > 1) || (swaps == true) ){ |
|||
if (gap > 1) |
|||
gap = static_cast<difference_type>(gap/shrink_factor); |
|||
swaps = false; |
|||
ForwardIterator itLeft(first); |
|||
ForwardIterator itRight(first); std::advance(itRight, gap); |
|||
for ( ; itRight!=last; ++itLeft, ++itRight ){ |
|||
if ( (*itRight) < (*itLeft) ){ |
|||
std::iter_swap(itLeft, itRight); |
|||
swaps = true; |
|||
} |
|||
} |
|||
} |
|||
}</lang> |
}</lang> |
||
Line 411: | Line 384: | ||
} |
} |
||
return input; |
return input; |
||
} |
|||
} |
|||
}</lang> |
|||
=={{header|C++}}== |
|||
This is copied from [[wp:Comb sort|the Wikipedia article]]. |
|||
<lang cpp>template<class ForwardIterator> |
|||
void combsort ( ForwardIterator first, ForwardIterator last ) |
|||
{ |
|||
static const double shrink_factor = 1.247330950103979; |
|||
typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type; |
|||
difference_type gap = std::distance(first, last); |
|||
bool swaps = true; |
|||
while ( (gap > 1) || (swaps == true) ){ |
|||
if (gap > 1) |
|||
gap = static_cast<difference_type>(gap/shrink_factor); |
|||
swaps = false; |
|||
ForwardIterator itLeft(first); |
|||
ForwardIterator itRight(first); std::advance(itRight, gap); |
|||
for ( ; itRight!=last; ++itLeft, ++itRight ){ |
|||
if ( (*itRight) < (*itLeft) ){ |
|||
std::iter_swap(itLeft, itRight); |
|||
swaps = true; |
|||
} |
|||
} |
} |
||
} |
} |
||
Line 621: | Line 621: | ||
-7 1 2 5 7 95 99 |
-7 1 2 5 7 95 99 |
||
</pre> |
</pre> |
||
=={{header|Elena}}== |
=={{header|Elena}}== |
||
ELENA 5.0 : |
ELENA 5.0 : |
||
Line 1,005: | Line 1,006: | ||
2,11,17,19,24,25,28,29,36,44,46,77,98,102,111,120,123,147,154,171,183,191,205,211,226,249,448 |
2,11,17,19,24,25,28,29,36,44,46,77,98,102,111,120,123,147,154,171,183,191,205,211,226,249,448 |
||
</pre> |
</pre> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
<lang go>package main |
<lang go>package main |
||
Line 1,202: | Line 1,204: | ||
Sorted Strings: [We,all,are,be,created,equal,hold,men,self-evident,that,these,to,truths] |
Sorted Strings: [We,all,are,be,created,equal,hold,men,self-evident,that,these,to,truths] |
||
</pre> |
</pre> |
||
=={{header|Io}}== |
|||
<lang io>List do( |
|||
combSortInPlace := method( |
|||
gap := size |
|||
swap := true |
|||
while(gap > 1 or swap, |
|||
swap = false |
|||
gap = (gap / 1.25) floor |
|||
for(i, 0, size - gap, |
|||
if(at(i) > at(i + gap), |
|||
swap = true |
|||
swapIndices(i, i + gap) |
|||
) |
|||
) |
|||
) |
|||
self) |
|||
) |
|||
lst := list(23, 76, 99, 58, 97, 57, 35, 89, 51, 38, 95, 92, 24, 46, 31, 24, 14, 12, 57, 78) |
|||
lst combSortInPlace println # ==> list(12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99)</lang> |
|||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |
||
Line 1,258: | Line 1,237: | ||
on string : "qwerty" |
on string : "qwerty" |
||
with op = &null: "eqrtwy" (0 ms)</pre> |
with op = &null: "eqrtwy" (0 ms)</pre> |
||
=={{header|Io}}== |
|||
<lang io>List do( |
|||
combSortInPlace := method( |
|||
gap := size |
|||
swap := true |
|||
while(gap > 1 or swap, |
|||
swap = false |
|||
gap = (gap / 1.25) floor |
|||
for(i, 0, size - gap, |
|||
if(at(i) > at(i + gap), |
|||
swap = true |
|||
swapIndices(i, i + gap) |
|||
) |
|||
) |
|||
) |
|||
self) |
|||
) |
|||
lst := list(23, 76, 99, 58, 97, 57, 35, 89, 51, 38, 95, 92, 24, 46, 31, 24, 14, 12, 57, 78) |
|||
lst combSortInPlace println # ==> list(12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99)</lang> |
|||
=={{header|IS-BASIC}}== |
=={{header|IS-BASIC}}== |
||
Line 2,031: | Line 2,033: | ||
return @arr; |
return @arr; |
||
}</lang> |
}</lang> |
||
=={{header|Perl 6}}== |
|||
{{trans|Perl}} |
|||
<lang perl6>sub comb_sort ( @a is copy ) { |
|||
my $gap = +@a; |
|||
my $swaps = 1; |
|||
while $gap > 1 or $swaps { |
|||
$gap = ( ($gap * 4) div 5 ) || 1 if $gap > 1; |
|||
$swaps = 0; |
|||
for ^(+@a - $gap) -> $i { |
|||
my $j = $i + $gap; |
|||
if @a[$i] > @a[$j] { |
|||
@a[$i, $j] .= reverse; |
|||
$swaps = 1; |
|||
} |
|||
} |
|||
} |
|||
return @a; |
|||
} |
|||
my @weights = (^50).map: { 100 + ( 1000.rand.Int / 10 ) }; |
|||
say @weights.sort.Str eq @weights.&comb_sort.Str ?? 'ok' !! 'not ok'; |
|||
</lang> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Line 2,266: | Line 2,244: | ||
</lang> |
</lang> |
||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
Line 2,288: | Line 2,265: | ||
[swaps]))))) |
[swaps]))))) |
||
xs) |
xs) |
||
</lang> |
|||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
{{trans|Perl}} |
|||
<lang perl6>sub comb_sort ( @a is copy ) { |
|||
my $gap = +@a; |
|||
my $swaps = 1; |
|||
while $gap > 1 or $swaps { |
|||
$gap = ( ($gap * 4) div 5 ) || 1 if $gap > 1; |
|||
$swaps = 0; |
|||
for ^(+@a - $gap) -> $i { |
|||
my $j = $i + $gap; |
|||
if @a[$i] > @a[$j] { |
|||
@a[$i, $j] .= reverse; |
|||
$swaps = 1; |
|||
} |
|||
} |
|||
} |
|||
return @a; |
|||
} |
|||
my @weights = (^50).map: { 100 + ( 1000.rand.Int / 10 ) }; |
|||
say @weights.sort.Str eq @weights.&comb_sort.Str ?? 'ok' !! 'not ok'; |
|||
</lang> |
</lang> |
||
Line 2,428: | Line 2,430: | ||
<pre>[12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99]</pre> |
<pre>[12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99]</pre> |
||
=={{header|Scala}}== |
|||
===Imperative version (Ugly, side effects)=== |
|||
<lang Scala>object CombSort extends App { |
|||
val ia = Array(28, 44, 46, 24, 19, 2, 17, 11, 25, 4) |
|||
val ca = Array('X', 'B', 'E', 'A', 'Z', 'M', 'S', 'L', 'Y', 'C') |
|||
def sorted[E](input: Array[E])(implicit ord: Ordering[E]): Array[E] = { |
|||
import ord._ |
|||
var gap = input.length |
|||
var swapped = true |
|||
while (gap > 1 || swapped) { |
|||
if (gap > 1) gap = (gap / 1.3).toInt |
|||
swapped = false |
|||
for (i <- 0 until input.length - gap) |
|||
if (input(i) >= input(i + gap)) { |
|||
val t = input(i) |
|||
input(i) = input(i + gap) |
|||
input(i + gap) = t |
|||
swapped = true |
|||
} |
|||
} |
|||
input |
|||
} |
|||
println(s"Unsorted : ${ia.mkString("[", ", ", "]")}") |
|||
println(s"Sorted : ${sorted(ia).mkString("[", ", ", "]")}\n") |
|||
println(s"Unsorted : ${ca.mkString("[", ", ", "]")}") |
|||
println(s"Sorted : ${sorted(ca).mkString("[", ", ", "]")}") |
|||
}</lang> |
|||
{{Out}}See it in running in your browser by [https://scalafiddle.io/sf/7ykMPZx/0 ScalaFiddle (JavaScript)] or by [https://scastie.scala-lang.org/Gp1ZcxnPQAKvToWFZLU7OA Scastie (JVM)]. |
|||
=={{header|Sather}}== |
=={{header|Sather}}== |
||
<lang sather>class SORT{T < $IS_LT{T}} is |
<lang sather>class SORT{T < $IS_LT{T}} is |
||
Line 2,498: | Line 2,468: | ||
end; |
end; |
||
end;</lang> |
end;</lang> |
||
=={{header|Scala}}== |
|||
===Imperative version (Ugly, side effects)=== |
|||
<lang Scala>object CombSort extends App { |
|||
val ia = Array(28, 44, 46, 24, 19, 2, 17, 11, 25, 4) |
|||
val ca = Array('X', 'B', 'E', 'A', 'Z', 'M', 'S', 'L', 'Y', 'C') |
|||
def sorted[E](input: Array[E])(implicit ord: Ordering[E]): Array[E] = { |
|||
import ord._ |
|||
var gap = input.length |
|||
var swapped = true |
|||
while (gap > 1 || swapped) { |
|||
if (gap > 1) gap = (gap / 1.3).toInt |
|||
swapped = false |
|||
for (i <- 0 until input.length - gap) |
|||
if (input(i) >= input(i + gap)) { |
|||
val t = input(i) |
|||
input(i) = input(i + gap) |
|||
input(i + gap) = t |
|||
swapped = true |
|||
} |
|||
} |
|||
input |
|||
} |
|||
println(s"Unsorted : ${ia.mkString("[", ", ", "]")}") |
|||
println(s"Sorted : ${sorted(ia).mkString("[", ", ", "]")}\n") |
|||
println(s"Unsorted : ${ca.mkString("[", ", ", "]")}") |
|||
println(s"Sorted : ${sorted(ca).mkString("[", ", ", "]")}") |
|||
}</lang> |
|||
{{Out}}See it in running in your browser by [https://scalafiddle.io/sf/7ykMPZx/0 ScalaFiddle (JavaScript)] or by [https://scastie.scala-lang.org/Gp1ZcxnPQAKvToWFZLU7OA Scastie (JVM)]. |
|||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
Line 2,689: | Line 2,692: | ||
<pre>45, 414, 862, 790, 373, 961, 871, 56, 949, 364 |
<pre>45, 414, 862, 790, 373, 961, 871, 56, 949, 364 |
||
45, 56, 364, 373, 414, 790, 862, 871, 949, 961</pre> |
45, 56, 364, 373, 414, 790, 862, 871, 949, 961</pre> |
||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|D}} |
{{trans|D}} |