This is an interesting program on finding the time for a sort of
huge data of one lac numbers
in variouus soting techniques Viz.
Selection/exahange sort,
Merge sort and
Built in Library sort in javascript and also in PYTHON,
with the identical coding.
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<script src="../jquery-1.11.1.js" ></script>
<script>
function mergesort(ar,start,end)
{
var s=start;
var n=2;
var e=s+n;
var tmp=[];
while (s<end)
{
var half=s+Math.floor(n/2);
if (half>end) half=end;
var j=half;
i=s;
while (i<half)
{
if (j<e && ar[j]<ar[i])
{
tmp.push(ar[j]);
j++;
}
else
{
tmp.push(ar[i]);
i++;
}
}
while (j<e)
{
tmp.push(ar[j]);
j++;
}
while (i<half)
{
tmp.push(ar[i]);
i++;
}
for (var k=0;k<tmp.length;k++)
{
ar[s+k]=tmp[k]
}
tmp=[];
s=s+n;
if (s < end && n < ar.length)
{
e=e+n;
if (e>end) e=end;
continue;
}
if (s>=end && n < ar.length)
{
n*=2;
s=start;
e=s+n;
if (e>end) e=end;
continue
}
}
}
function selsort(ar,start,end)
{
for (var i=0;i<end;i++)
{
for (var j=i;j<end;j++)
{
if (ar[j]<ar[i])
{
var t=ar[i]; ar[i]=ar[j]; ar[j]=t;
}
}
}
}
function startme()
{
A=[];
B=[];
C=[];
for (var x=100000;x>0;x--)
{
A.push(x); B.push(x); C.push(x);
}
//$('#out').append(A.join(' '));
//$('#out').append("<br>");
var t1 = new Date();
selsort(A,0,A.length);
var t2 = new Date();
var dif = t2.getTime() - t1.getTime();
$('#out').prepend("SELECTION/EXCHANGE SORT time = "+dif+" milli seconds <br>");
var t1 = new Date();
mergesort(B,0,B.length);
var t2 = new Date();
var dif = t2.getTime() - t1.getTime();
$('#out').prepend("MERGE SORT time = "+dif+" milli seconds <br>");
//$('#out').append(B.join(' '));
//$('#out').append("<br>");
var t1 = new Date();
C.sort();
var t2 = new Date();
var dif = t2.getTime() - t1.getTime();
$('#out').prepend("Javascript Built in library SORT time = "+dif+" milli seconds <br>");
}
</script>
</head>
<body onload='startme()'>
<div id='out'></div>
<div id='js'>
<pre>
</pre>
</div>
</body>
</html>
/******* PYTHON FULL PROGRAM ************/
import time
#selection sort
def selsort(ar,start,end):
for i in range(start,end):
for j in range (i,end):
if ar[j]<ar[i]:
ar[i],ar[j]=ar[j],ar[i]
A=[x for x in range(100000,0,-1)]
print(A[0:5],'...', A[-5:])
stime=time.time()
selsort(A,0,len(A))
print(A[0:5],'...', A[-5:])
etime=time.time()
print("Selection sort time ",(etime - stime)*1000 , "milli seconds")
"""
MERGE SORT ROUTINES FOR SAME DATA IN ALREADY SORTED ORDER
"""
def mergesort(ar,start,end):
s=start
n=2
e=s+n
tmp=[]
while s<end:
#half=s+(e-s)//2
half=s+n//2
if half>end:
half=end
j=half
i=s
while (i<half): #for i in range(s,half):
if j<e and ar[j]<ar[i]:
tmp.append(ar[j])
j=j+1
else:
tmp.append(ar[i])
i=i+1
while (j<e):
tmp.append(ar[j])
j=j+1
while (i<half):
tmp.append(ar[i])
i=i+1
for k in range(len(tmp)):
ar[s+k]=tmp[k]
if (1) : ## debug statements turned to false
#print(tmp,'n=',n,'half=' ,half, 'start', s,'end', e,ar)
# input('?')
pass
tmp=[]
s=s+n
#print("???", s<end and n<len(ar))
if s<end and n<len(ar):
e=e+n
if e>end:
e=end
continue
#print(s>=end and n<len(ar))
if s>=end and n<len(ar):
n*=2
s=start
e=s+n
if e>end:
e=end
continue
A=[x for x in range(100000,0,-1)]
B=A.copy()
print(A[0:5],'...', A[-5:])
stime=time.time()
mergesort(A,0,len(A))
etime=time.time()
print("Merge sort time ",(etime - stime)*1000 , "milli seconds")
print(A[0:5],'...', A[-5:])
#### builtin library sort
stime=time.time()
print(B[0:5],'...', B[-5:])
B.sort()
etime=time.time()
print("Built in library sort time ",(etime - stime)*1000 , "milli seconds")
print(B[0:5],'...', B[-5:])
#### Sample output
# Ding! public_html/bnvenkat.com/apy2> python3 practicaltime_sort.py
# [100000, 99999, 99998, 99997, 99996] ... [5, 4, 3, 2, 1]
# [1, 2, 3, 4, 5] ... [99996, 99997, 99998, 99999, 100000]
# Selection sort time 609906.2340259552 milli seconds
# [100000, 99999, 99998, 99997, 99996] ... [5, 4, 3, 2, 1]
# Merge sort time 447.0195770263672 milli seconds
# [1, 2, 3, 4, 5] ... [99996, 99997, 99998, 99999, 100000]
# [100000, 99999, 99998, 99997, 99996] ... [5, 4, 3, 2, 1]
# Built in library sort time 1.2576580047607422 milli seconds
# [1, 2, 3, 4, 5] ... [99996, 99997, 99998, 99999, 100000]
# 18:22 public_html/bnvenkat.com/apy2>
#
# /************* TIMINGS IN PYTHON FOR IDENTICAL INPUTS in both JS and PYTHON ***********/
# inference:
# The selection sort takes approximaltely 600 seconds
# while the my mergesort has taken 447 milli seconds
# and buitin library sort has taken less than 1.25 milli second
SAMPLE OUTPUT IN JAVASCRIPT
Javascript Built in library SORT time = 4 milli seconds
MERGE SORT time = 33 milli seconds
SELECTION/EXCHANGE SORT time = 6209 milli seconds or 6.209 seconds