Compare sorting algorithms' performance: Difference between revisions
Content added Content deleted
Line 1,700: | 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. |
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}}== |
=={{header|Phix}}== |