-
Notifications
You must be signed in to change notification settings - Fork 0
/
qsort.nim
64 lines (51 loc) · 1.52 KB
/
qsort.nim
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import lists,
random,
math
proc fillUnsortedList(unsortedItems : var seq[int]) =
var i = 0
while i < unsortedItems.len :
unsortedItems[i] = random(10)
inc(i)
proc getMediana(unsortedItems : seq[int], l, r : int) : int =
var min, max = unsortedItems[l]
var i = l
while i < r :
var item = unsortedItems[i]
if item < min :
min = item
else:
if item > max :
max = item
inc(i)
((max + min) / 2).int
proc quicksort(unsortedItems : var seq[int]) =
var operations = initDoublyLinkedList[tuple[l : int, r : int]]()
prepend(operations, (l : 0, r : unsortedItems.high))
while operations.head != nil :
var operation = operations.head.value
remove(operations, operations.head)
var left = operation.l
var right = if operation.r >= 0 : operation.r else : unsortedItems.high
if (right - left + 1) < 2 :
continue
var mediana = getMediana(unsortedItems, left, right)
while left <= right :
if unsortedItems[left] < mediana :
inc(left)
continue
if unsortedItems[right] > mediana :
dec(right)
continue
if left <= right:
swap(unsortedItems[left], unsortedItems[right])
inc(left)
dec(right)
prepend(operations, (l : operation.l, r : right))
prepend(operations, (l : left, r : operation.r))
proc main() =
var unsortedItems = newSeq[int](100)
fillUnsortedList(unsortedItems)
echo unsortedItems
quicksort(unsortedItems)
echo unsortedItems
main()