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

Sortieralgorithmen zur Übung

Beitragvon nofuture » 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

Re: Sortieralgorithmen zur Übung

Beitragvon 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

Beitragvon nofuture » Montag 7. August 2006, 17:01

Gut, werde mir PEP 8 anschauen.

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

Beitragvon 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

Beitragvon nofuture » 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"?
Benutzeravatar
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Beitragvon Joghurt » 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]

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder