Das deutsche Python-Forum

Code: Alles auswählen

def createRandomList(param):
    return [random.randrange(100) for x in xrange(param)]
    
def createEmptyList(param):
	return [0 for x in xrange(param)]  

Code: Alles auswählen

import random
import listutil

def insertionSort(A):
	for j in xrange(len(A)):
		key = A[j]
		i = j-1
		while i >= 0 and A[i]>key:
			A[i+1] = A[i]
			i = i-1
		A[i+1] = key
		
if __name__ == "__main__":
	length = 10
	A = createRandomList(length)
	print ' '.join([str(x) for x in A]) 
	insertionSort(A)	
	print ' '.join([str(x) for x in A])	

Code: Alles auswählen

import random
import listutil
    
def merge(A, p, q, r):
	n1 = q-p+1
	n2 = r-q

       # 2 neue Arrays , +1 für einen Merker
	L = createEmptyList(n1+1)
	R = createEmptyList(n2+1)

	for i in xrange(n1):
		L[i] = A[p+i-1]
	for j in xrange(n2):
		R[j] = A[q+j]
	
	L[n1] = 1001 # 1001 als sentinel
	R[n1] = 1001
	i=0
	j=0
	k=p
	for k in range(r-p):
		if L[i] <= R[j]:
			A[k] = L[i]
			i +=1
		else:
			A[k] = R[j]
			j +=1
		
def mergeSort(A,p,r):
	if p < r:
		q=(p+r)//2    #Teile in der Mitte

		mergeSort(A,p,q) # Sortiere Hälfte 1
		mergeSort(A,q+1,r) # Hälfte 2

		merge(A,p,q,r) # füge zusammen
		
if __name__ == "__main__":
	length = 10
	a = createRandomList(length)
	print ' '.join([str(x) for x in a]) 
	
	mergeSort(a, 0, 30)
	print ' '.join([str(x) for x in a])	

Code: Alles auswählen

L = A[p-1:q]
R = A[q:r]