import time
from random import randint
def max_n_1(arr,n):
    return sorted(arr,reverse=True)[0:n]
def max_n_2(arr,n):
    res=[-1 for _ in range(n)]
    for x in arr:
        if x > res[n-1]:
            i=n-1
            j=i-1
            while(j>=0 and res[j]<x):
                res[i]=res[j]
                i=i-1
                j=j-1
            res[i]=x
    return res
def start():
    k=10
    n=10000
    print("k=",k)
    while(n<=500000):
        print("n=",n,end=' ')
        t1=0.0
        for i in range(10):
            arr=[randint(1,2000) for _ in range(n)]
            start_time = time.time()
            z1=max_n_1(arr,k)
            fin_time = time.time()
            t1=t1+(fin_time-start_time)
        print(t1/10.0,end=' ')
        t2=0.0
        for i in range(10):
            arr=[randint(1,2000) for _ in range(n)]
            start_time = time.time()
            z2=max_n_2(arr,k)
            fin_time = time.time()
            t2=t2+(fin_time-start_time)
        print(t2/10.0)
        n+=10000
start()

import java.util.*;
class Start
{
   public static void main(String [] args)
   {
    Random random = new Random();
    Scanner inp = new Scanner(System.in);
    long startTime,endTime,tot1,tot2;
    int i,a,b,n,m,x,ii,jj,u;
    a=1;
    b=3000; // диапазон случайных чисел [a,b]
    m=10;
    System.out.println(a+" "+b+" "+m);
    for (n=50000; n<=5000000; n+=50000)
    {
      int arr[] = new int[n];
      int ma[]  = new int[m];
      tot1=0;
      for (u=0; u<10; u++)
      {
        for (i=0; i<n; i++)
        {
         arr[i]=a+random.nextInt(b-a+1);
        }
        startTime = System.currentTimeMillis();
        Arrays.sort(arr);
        endTime = System.currentTimeMillis();
        tot1=tot1+(endTime-startTime);
      }
      tot2=0;
      for (u=0; u<10; u++)
      {
        for (i=0; i<n; i++)
        {
          arr[i]=a+random.nextInt(b-a+1);
        }
        startTime = System.currentTimeMillis();
        for (i=0; i<m; i++) ma[i]=-999999;
        for (i=0; i<n; i++)
        {
            x=arr[i];
            if (x >= ma[m-1])
            {
              ii=m-1;
              jj=ii-1;
              while(jj>=0 && ma[jj]<x)
              {
                ma[ii]=ma[jj];
                ii--;
                jj--;
              }
              ma[ii]=x;
            }
          }
          endTime = System.currentTimeMillis();
          tot2=tot2+(endTime-startTime);
        }
      System.out.println(n+" "+tot1+" "+tot2);
    }
  }
}

Private Declare Function GetTickCount Lib "kernel32" () As Long
'::: Собственно сортировка
Sub QSort(A() As Long, Optional b As Long = 1, Optional e As Long = 0)
    If b > e Then Exit Sub
    i& = b
    j& = e
    w& = A((i& + j&) / 2)
    Do While (True)
      Do While (A(i&) < w&)
         i& = i& + 1
      Loop
      Do While (A(j&) > w&)
         j& = j& - 1
      Loop
      If i& <= j& Then
         Tmp& = A(i&)
         A(i&) = A(j&)
         A(j&) = Tmp&
         i& = i& + 1
         j& = j& - 1
      End If
      If i& > j& Then Exit Do
    Loop
    If j& > b Then QSort A, b, j&
    If i& < e Then QSort A, i&, e
End Sub
'::: Проверка успешности сортировки
Function check(X() As Long) As Boolean
     n& = UBound(X)
     For i& = 1 To n& - 1
         If X(i& + 1) < X(i&) Then
            Debug.Print "Err! i=" + CStr(i&)
            check = False
            Exit Function
         End If
     Next i&
     check = True
End Function
'::: Вставка в упорядоченный массив
Sub ins_in_arr(X As Long, A() As Long, n As Integer)
    If X < A(n) Then Exit Sub
    For i% = 1 To n
        If X > A(i%) Then
           For j% = n To i% + 1 Step -1
               A(j%) = A(j% - 1)
           Next j%
           A(i%) = X
           Exit Sub
        End If
    Next i%
End Sub
'::: Собственно тест
Sub test()
Const sz = 500
Dim X() As Long
Dim Ma(1 To sz) As Long
    Randomize
    ooo& = 1
    For n& = 10000 To 500000 Step 10000
        t1# = 0
        For nc% = 1 To 10
            ReDim X(1 To n&) As Long
            For i& = 1 To n&
                X(i&) = Rnd() * 5000
            Next i&
            s1& = GetTickCount
            For i& = 1 To sz
                Ma(i&) = -2147483647
            Next i&
            For i& = 1 To n&
                ins_in_arr X(i&), Ma, 10
            Next i&
            s2& = GetTickCount
            t1# = t1# + s2& - s1&
        Next nc%
        Cells(ooo&, 1).Value = n&
        Cells(ooo&, 2).Value = t1# / 10
        t2# = 0
        For nc% = 1 To 10
            ReDim X(1 To n&) As Long
            For i& = 1 To n&
                X(i&) = Rnd() * 5000
            Next i&
            s1& = GetTickCount
            QSort X, 1, n&
            s2& = GetTickCount
            If Not check(X) Then
               MsgBox "Ошибка при сортировке!"
               Exit Sub
            End If
            t2# = t2# + s2& - s1&
        Next nc%
        Cells(ooo&, 3).Value = t2# / 10
        ooo& = ooo& + 1
    Next n&
End Sub