Sortieralgorithmen zur Übung

[nofuture]

Util für Listen:

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)]  

Insertion Sort:

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])	

Bei Merge Sort hapert es gerade ein bißchen:
'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])	

[BlackJack]

Bei Merge Sort hapert es gerade ein bißchen:
'invalid syntax' '\t\tq=(p+r)//2'
Ich dachte // ist der ganzzahlige Divisor?

Ja, der Ausdruck selbst ist auch okay. Entweder benutzt Du ein zu altes Python oder Du mixt Leerzeichen und Tabs.

Und das sieht alles so "unpythonisch" aus. Wenigstens die Namensgebung könntest Du auf PEP 8 umstellen, also `insertion_sort()` statt `insertionSort()`.

[nofuture]

Gut, werde mir PEP 8 anschauen.

Was kann ich denn noch verbessern bzw. "pythonisieren"?

[BlackJack]

Einfach die `sort()` Methode oder `sorted()` benutzen. Was Du da geschrieben hast, sieht nach C oder Java aus.

[nofuture]

Deswegen steht in der Überschrift zur Übung. Welche Zeile sieht nach Java aus und wie kann ich sie "richtig schreiben"?

[Joghurt]

Deswegen steht in der Überschrift zur Übung. Welche Zeile sieht nach Java aus und wie kann ich sie "richtig schreiben"?

Erstmal macht createEmptyList keine leere Liste, sondern eine Liste mit Nullen.

Und du kannst z.B. statt

Code: Alles auswählen

	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]

einfach folgendes schreiben:

Code: Alles auswählen

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