Sortieralgorithmen zur Übung

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
nofuture
User
Beiträge: 16
Registriert: Montag 31. Juli 2006, 22:59

Montag 7. August 2006, 13:36

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

Montag 7. August 2006, 14:47

nofuture hat geschrieben: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
User
Beiträge: 16
Registriert: Montag 31. Juli 2006, 22:59

Montag 7. August 2006, 17:01

Gut, werde mir PEP 8 anschauen.

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

Montag 7. August 2006, 20:29

Einfach die `sort()` Methode oder `sorted()` benutzen. Was Du da geschrieben hast, sieht nach C oder Java aus.
nofuture
User
Beiträge: 16
Registriert: Montag 31. Juli 2006, 22:59

Montag 7. August 2006, 20:34

Deswegen steht in der Überschrift zur Übung. Welche Zeile sieht nach Java aus und wie kann ich sie "richtig schreiben"?
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Montag 7. August 2006, 20:54

nofuture hat geschrieben: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]
Antworten