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

def loadArray(filename):
	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():
	A = loadArray('Q8.txt')
	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)


	A = loadArray('Q8.txt')
	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)


	A = loadArray('Q8.txt')
	print 'brute force counting...'
	imcount = bruteCount(A)
	print 'bruteCount: {}.'.format(imcount)


if __name__ == '__main__':
	main()

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).