Sorting algorithms/Quicksort: Difference between revisions

Content added Content deleted

Inline

@@ Line 2,782: / Line 2,782: @@
 =={{header|Nimrod}}==
+<lang nimrod>
-<lang python>proc QuickSort(list: seq[int]): seq[int] =
+proc quickSort[T](a: var seq[T], inl = 0, inr = -1) =
-    if len(list) == 0:
-        return @[]
+  var r = if inr >= 0: inr else: a.high
+  var l = inl
-    var pivot = list[0]
+  let n = r - l + 1
+  if n < 2: return
-    var left: seq[int] = @[]
+  let p = a[l + 3 * n div 4]
+  while l <= r:
-    var right: seq[int] = @[]
+    if a[l] < p:
-    for i in low(list)+1..high(list):
-        if list[i] <= pivot:
+      inc l
-            left.add(list[i])
+      continue
-        elif list[i] > pivot:
+    if a[r] > p:
-            right.add(list[i])
+      dec r
+      continue
-    result = QuickSort(left)
+    if l <= r:
+      swap a[l], a[r]
-    result.add(pivot)
+      inc l
-    result.add(QuickSort(right))</lang>
+      dec r
+  quickSort(a, inl, r)
+  quickSort(a, l, inr)
+var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
-Usage:
+quickSort a
-<lang python>var sorted: seq[int] = QuickSort(@[5,2,1,6,2,3,1,2,123,21,54,6,1])
+echo a</lang>
-for i in items(sorted):
+Output:
-  echo(i)</lang>
+<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>
 =={{header|Objeck}}==