#C2.txt Math640(Spring 2019) Dr. Z.
Help:=proc(): print(` Qs(L) , TestS(n,K,T,f) , QsC(L), PQs(n,t) `): end:




#######start C1.txt
#Jan. 24, 2019 C1.txt getting started
Help1:=proc(): print(` OurMin(L); SelS(L);  `): end:

#OurMin(L):inputs a list of numbers and outputs the smallest entry and location
OurMin:=proc(L) local i ,n, rec,champ:
n:=nops(L):
rec:=L[1]:
champ:=1:

for i from 2 to n do
 if L[i]<rec then
   rec:=L[i]:
   champ:=i:
 fi:
od:

RETURN(rec,champ):
end:

SelS:=proc(L) local L1,NewL,i,n,mi,champ:
 n:=nops(L):
 NewL:=[]:
 L1:=L:

 for i from 1 to n do
 mi:=OurMin(L1)[1]:
 champ:=OurMin(L1)[2]:
 NewL:=[op(NewL),mi]:
 L1:=[op(1..champ-1,L1), op(champ+1..nops(L1),L1)]:
 
 od:
NewL:

end:

################end of C1.txt
 
  #Qs(L): inputs a list of numbers and outputs the sorted list (in increasing order)
  Qs:=proc(L) local n,p,v,L1,L2,i:
   n:=nops(L):
  
   if n=0 or n=1 then
      RETURN(L):
   fi:

 p:=rand(1..n)():
  v:=L[p]:

   L1:=[]: #L1 is the list of mebers of L smaller then v
   L2:=[]: #L2 .... >=0 then v
 
 for i from 1 to n do
    if i<>p then
      if L[i]<v then
        L1:=[op(L1),L[i]]:
       else
         L2:=[op(L2),L[i]]:
      fi:
    fi:
  od:

 [op(Qs(L1)),v, op(Qs(L2))]:

   end:
 
 #TestS(n,K,T,f): inputs a positive integer n (the length of the list) K (the upper bound)), T
 #the number of times to run it, and f the function (sort, Qs, SelS)1
 TestS:=proc(n,K,T,f) local  RT,ra,i,j,L:
  ra:=rand(1..K):
  RT:=[]:
   

   for i from 1 to T do
     L:=[seq(ra(),j=1..n)]:
     RT:=[op(RT),time(f(L))]:
    od: 
   
 sort(RT), convert(RT,`+`)/T :  
 end:


#QsC(L): inputs a list of numbers and outputs the sorted list (in increasing order)
#and also returns the number of comparisons
  QsC:=proc(L) local n,p,v,L1,L2,i:
   option remember:
   n:=nops(L):
  
   if n=0 or n=1 then
      RETURN(L,0):
   fi:

 p:=rand(1..n)():
  v:=L[p]:

   L1:=[]: #L1 is the list of mebers of L smaller then v
   L2:=[]: #L2 .... >=0 then v
 
 for i from 1 to n do
    if i<>p then
      if L[i]<v then
        L1:=[op(L1),L[i]]:
       else
         L2:=[op(L2),L[i]]:
      fi:
    fi:
  od:

 [op(QsC(L1)[1]),v, op(QsC(L2)[1])], n-1+QsC(L1)[2]+QsC(L2)[2] :

   end:

 #PQs(n,t):the prob. generating function of the running time of Quicksort
 PQs:=proc(n,t) local k:
   option remember:
  if n=0 or n=1 then
   RETURN(1):
  else:

  RETURN(expand(t^(n-1)*add(1/n*PQs(k-1,t)*PQs(n-k,t),k=1..n))):
 fi:

 end: