fork download
copy 
  1. # your code goes here
  2. def orderStat(A, l, r, K):
  3.     k = K - 1
  4.     #if l == r:
  5.     #    return A[l]
  6.     if r - l <= 25:
  7.         order5(A, l, r)
  8.         return(A[k])
  9.     m = (r - l)//5 + 1
  10.     #test
  11.     print('m is', m)
  12.     #
  13.     B = []
  14.     for i in range(m):
  15.         B[i] = orderStat(A, 5*i, min(5*i+4,len(A)-1), 3)
  16.     mom = orderStat(B, 0, len(B)-1, len(B)//2)
  17.  
  18.     p = partition(A, l, r)
  19.     pl = p - l + 1
  20.  
  21.     if k < pl:
  22.         return orderStat(A, l, p-1, K)
  23.     elif k > pl:
  24.         return orderStat(A, p+1, r, K - p -1)     
  25.     else:
  26.         return mom
  27.     pass
  28.  
  29. def partition(A, l, r):
  30.     x = A[l]
  31.     i = l
  32.     for j in range(l+1, r):
  33.         if A[j] <= x:
  34.             i += 1
  35.             A[i],A[j] = A[j],A[i]
  36.     A[i],A[l] = A[l],A[i]
  37.  
  38.     return i
  39.  
  40.     pass
  41. # Return the approximate median among elements A[l ... r]
  42. def approxMed(A, l, r):
  43.     pass
  44.  
  45. # Rearrange A[start, start+1, ..., min(start+4, len(A)-1)] in ascending order
  46. def order5(A, start, stop):
  47.     i = start+1
  48.     for i in range(start+1, min(stop+1, len(A))):
  49.         j = i
  50.         while start+1<=j and A[j-1]>A[j]:
  51.             A[j-1],A[j] = A[j],A[j-1]
  52.             j -= 1
  53.  
  54. list = [1,2,3,4,5,6,7,8,9,10,11,14,15,16,18,19,20,22,26,28,29,30,37,38,39,50,52,127,46,48]
  55. #result = order5(list, 0, len(list)-1)
  56. result = orderStat(list, 0, len(list)-1, 5)
  57. print(result)
Runtime error #stdin #stdout #stderr 0.01s 27704KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
m is 6
stderr
copy 
Traceback (most recent call last):
  File "./prog.py", line 56, in <module>
  File "./prog.py", line 15, in orderStat
IndexError: list assignment index out of range
https://ideone.com/cE8awE
language:
Python 3 (python  3.9.5)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!