Averages/Median: Difference between revisions

Content added Content deleted

Inline

@@ Line 2,485: / Line 2,485: @@
 <syntaxhighlight lang="text">
 proc quickselect k . list[] res .
-  #
+   #
-  subr partition
+   subr partition
-    mid = left
+      mid = left
-    for i = left + 1 to right
+      for i = left + 1 to right
-      if list[i] < list[left]
+         if list[i] < list[left]
-        mid += 1
+            mid += 1
-        swap list[i] list[mid]
+            swap list[i] list[mid]
+         .
       .
+      swap list[left] list[mid]
-    .
+   .
-    swap list[left] list[mid]
+   left = 1
-  .
-  left = 1
+   right = len list[]
+   while left < right
-  right = len list[]
+      partition
-  while left < right
-    call partition
+      if mid < k
-    if mid < k
+         left = mid + 1
-      left = mid + 1
+      elif mid > k
-    elif mid > k
+         right = mid - 1
-      right = mid - 1
+      else
+         left = right
-    else
-      left = right
+      .
-    .
+   .
+   res = list[k]
-  .
-  res = list[k]
 .
 proc median . list[] res .
-  h = len list[] div 2 + 1
+   h = len list[] div 2 + 1
-  call quickselect h list[] res
+   quickselect h list[] res
-  if len list[] mod 2 = 0
+   if len list[] mod 2 = 0
-    call quickselect h - 1 list[] h
+      quickselect h - 1 list[] h
-    res = (res + h) / 2
+      res = (res + h) / 2
-  .
+   .
 .
 test[] = [ 4.1 5.6 7.2 1.7 9.3 4.4 3.2 ]
-call median test[] med
+median test[] med
 print med
 test[] = [ 4.1 7.2 1.7 9.3 4.4 3.2 ]
-call median test[] med
+median test[] med
 print med
 </syntaxhighlight>