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])
'invalid syntax' '\t\tq=(p+r)//2'
Ich dachte // ist der ganzzahlige Divisor?
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])