# Demo entry 6646007

sort_and_count

Submitted by anonymous on Oct 12, 2017 at 16:21
Language: Python. Code size: 1.7 kB.

```import os
import random
import time

l = []
with open(filename,'r') as f:
for line in f:
l.append(int(line.strip()))
return l

def validate(A):
for i in xrange(1,len(A)):
if A[i] < A[i-1]:
return False
return True

def quicksort(A,s,e):
if s>=e:
return 0;
i = s
j = e
key = A[i]
while i<j:
while key<=A[j] and i<j:
j -= 1
A[i] = A[j]
while key>=A[i] and i<j:
i += 1
A[j] = A[i]
A[i] = key
quicksort(A,s,i)
quicksort(A,i+1,e)

def mergesort(A,s,e):
def merge(A,s,c,e):
L = A[s:c+1]
R = A[c+1:e+1]
i,j = 0,0
rc = 0
for k in xrange(s,e+1):
if i < len(L) and j < len(R):
if L[i]<=R[j]:
A[k] = L[i]
i += 1
else:
A[k] = R[j]
rc += len(L)-i
j += 1
else:
if j >= len(R):
A[k] = L[i]
i+=1
else:
A[k] = R[j]
j+=1
return rc

if s == e:
return 0;
cp = A[s:e+1]
rcl = mergesort(A,s,(s+e)//2)
rcr = mergesort(A,(s+e)//2+1,e)
rc = merge(A,s,(s+e)//2,e)
return rcl+rcr+rc

def bruteCount(A):
count = 0
for i in xrange(len(A)):
for j in xrange(i+1,len(A)):
if A[i]>A[j]:
count+=1
return count

def main():
print 'Quick sorting...'
start = time.time()
quicksort(A,0,len(A)-1)
end = time.time()
print len(A),validate(A)
print 'time cost/s: {}'.format(end-start)

print 'Merge sorting...'
start = time.time()
imcount = mergesort(A,0,len(A)-1)
end = time.time()
print len(A),validate(A)
print 'time cost/s: {}'.format(end-start)
print 'merge and count:{}.'.format(imcount)