Anonymous user
Compare sorting algorithms' performance: Difference between revisions
Compare sorting algorithms' performance (view source)
Revision as of 00:00, 9 November 2020
, 3 years ago→{{header|Kotlin}}
Line 1,700:
On the other hand, bubble and insertion sorts are much quicker than the other methods for constant data and for data which is already sorted in an ascending direction, bubble sort being the faster of the two.
=={{header|Nim}}==
{{trans|Kotlin}}
This is a direct translation of the Kotlin program. We have added the sorting algorithm provided by Nim standard library which is a merge sort. For this reason, we have been constrained to annotate the sorting functions with the pragma {.locks: "unknown".} to make their type compatible with that of the standard sort function.
We have also added the array as first parameter of the internal function “sorter” as Nim compiler doesn’t allow direct access to this mutable array in function “quicksort” (memory safety violation).
{lang Nim}import algorithm
import random
import sequtils
import times
####################################################################################################
# Data.
proc oneSeq(n: int): seq[int] = repeat(1, n)
#---------------------------------------------------------------------------------------------------
proc shuffledSeq(n: int): seq[int] =
result.setLen(n)
for item in result.mitems: item = rand(1..(10 * n))
#---------------------------------------------------------------------------------------------------
proc ascendingSeq(n: int): seq[int] = sorted(shuffledSeq(n))
####################################################################################################
# Algorithms.
func bubbleSort(a: var openArray[int]) {.locks: "unknown".} =
var n = a.len
while true:
var n2 = 0
for i in 1..<n:
if a[i - 1] > a[i]:
swap a[i], a[i - 1]
n2 = i
n = n2
if n == 0: break
#---------------------------------------------------------------------------------------------------
func insertionSort(a: var openArray[int]) {.locks: "unknown".} =
for index in 1..a.high:
let value = a[index]
var subIndex = index - 1
while subIndex >= 0 and a[subIndex] > value:
a[subIndex + 1] = a[subIndex]
dec subIndex
a[subIndex + 1] = value
#---------------------------------------------------------------------------------------------------
func quickSort(a: var openArray[int]) {.locks: "unknown".} =
func sorter(a: var openArray[int]; first, last: int) =
if last - first < 1: return
let pivot = a[first + (last - first) div 2]
var left = first
var right = last
while left <= right:
while a[left] < pivot: inc left
while a[right] > pivot: dec right
if left <= right:
swap a[left], a[right]
inc left
dec right
if first < right: a.sorter(first, right)
if left < last: a.sorter(left, last)
a.sorter(0, a.high)
#---------------------------------------------------------------------------------------------------
func radixSort(a: var openArray[int]) {.locks: "unknown".} =
var tmp = newSeq[int](a.len)
for shift in countdown(63, 0):
for item in tmp.mitems: item = 0
var j = 0
for i in 0..a.high:
let move = a[i] shl shift >= 0
let toBeMoved = if shift == 0: not move else: move
if toBeMoved:
tmp[j] = a[i]
inc j
else:
a[i - j] = a[i]
for i in j..tmp.high: tmp[i] = a[i - j]
for i in 0..a.high: a[i] = tmp[i]
#---------------------------------------------------------------------------------------------------
func shellSort(a: var openArray[int]) {.locks: "unknown".} =
const Gaps = [701, 301, 132, 57, 23, 10, 4, 1]
for gap in Gaps:
for i in gap..a.high:
let temp = a[i]
var j = i
while j >= gap and a[j - gap] > temp:
a[j] = a[j - gap]
dec j, gap
a[j] = temp
#---------------------------------------------------------------------------------------------------
func standardSort(a: var openArray[int]) =
a.sort()
####################################################################################################
# Main code.
import strformat
const
Runs = 10
Lengths = [1, 10, 100, 1_000, 10_000, 100_000]
Sorts = [bubbleSort, insertionSort, quickSort, radixSort, shellSort, standardSort]
const
SortTitles = ["Bubble", "Insert", "Quick ", "Radix ", "Shell ", "Standard"]
SeqTitles = ["All Ones", "Ascending", "Shuffled"]
var totals: array[SeqTitles.len, array[Sorts.len, array[Lengths.len, Duration]]]
randomize()
for k, n in Lengths:
let seqs = [oneSeq(n), ascendingSeq(n), shuffledSeq(n)]
for _ in 1..Runs:
for i, s in seqs:
for j, sort in Sorts:
var s = s
let t0 = getTime()
s.sort()
totals[i][j][k] += getTime() - t0
echo "All timings in microseconds\n"
stdout.write "Sequence length "
for length in Lengths:
stdout.write &"{length:6d} "
echo '\n'
for i in 0..SeqTitles.high:
echo &" {SeqTitles[i]}:"
for j in 0..Sorts.high:
stdout.write &" {SortTitles[j]:8s} "
for k in 0..Lengths.high:
let time = totals[i][j][k].inMicroseconds div Runs
stdout.write &"{time:8d} "
echo ""
echo '\n'</lang>
{{out}}
<pre>All timings in microseconds
Sequence length 1 10 100 1000 10000 100000
All Ones:
Bubble 0 0 0 0 6 64
Insert 0 0 0 1 9 90
Quick 0 0 3 9 105 1201
Radix 1 4 34 103 848 8354
Shell 0 0 2 10 97 946
Standard 0 2 2 6 45 380
Ascending:
Bubble 0 0 0 0 6 61
Insert 0 0 0 1 9 94
Quick 0 0 3 11 88 919
Radix 1 5 47 154 1435 15519
Shell 0 0 2 10 95 954
Standard 0 0 2 7 47 463
Shuffled:
Bubble 0 0 38 1026 133729 16181412
Insert 0 0 8 152 10010 1133210
Quick 0 0 9 63 607 7199
Radix 1 5 46 157 1405 15557
Shell 0 0 8 69 708 10236
Standard 0 0 18 96 992 12394</pre>
==={Conclusions}===
Compared to the results obtained by the Kotlin program, the radix sort seems less efficient and the shell sort more efficient. Maybe some optimizations could improve the radix sort, but it seems also that the shell sort is well optimized by the Nim compiler and the C compiler.
The standard sort behaves well if the list is already sorted. For random list, it is less efficient than the quick sort or the shell sort, but is still a good performer.
=={{header|Phix}}==
| |||