Sortieralgorithmus - Problem

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.
Sandra
User
Beiträge: 11
Registriert: Dienstag 30. September 2008, 12:44

Dienstag 30. September 2008, 13:14

Hi,

Ich bin im Grunde komplette Anfängerin was Programmieren und Python betrifft, daher hoffe ich, ihr könnt mir ein wenig helfen...

Wir haben die Aufgabe bekommen, eine Funktion zu schreiben, welche Daten sortieren kann.

Dazu habe ich auf Wikipedia (http://de.wikipedia.org/wiki/Python_(Pr ... ersprache)) diesen Code gefunden:

Code: Alles auswählen

def quicksort(liste):
    if len(liste) <= 1:
        return liste
    pivotelement = liste[0]
    links  = [element for element in liste[1:] if element <  pivotelement]
    rechts = [element for element in liste[1:] if element >= pivotelement]
    return quicksort(links) + [pivotelement] + quicksort(rechts)
doch was z.B.

Code: Alles auswählen

[element for element in liste[1:] if element <  pivotelement]
macht verstehe ich gar nicht. Was heißt element for element? oder [1:]?
Kann mir jemand in Worten die obigen Zeilen erklären?

mfg Sandra
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Dienstag 30. September 2008, 13:21

Als selbstbenannte Anfängerin würde ich einen anderen Weg gehen:
Zunächst einmal das Tutorial durcharbeiten und anschließend einmal selbst überlegen, wie man Daten, z.B. eine Liste von Werten, sortieren könnte.

Zum Beispiel, indem man immer das größte heraussucht und an den Anfang oder das Ende der Liste setzt. Oder aus der Liste entfernt und in eine andere Liste setzt. Das ist nicht effizient, aber leicht verständlich.

Dass Listen schon eine Methode zum Sortieren mitbringen, dürfte dir wenig helfen, weil ihr das ja selbst implementieren sollt.

Und wenn du schon einen fertigen Algorithmus verwenden und verstehen willst, dann fang vielleicht mit Bubblesort an und nicht mit Quicksort.
Benutzeravatar
name
User
Beiträge: 254
Registriert: Dienstag 5. September 2006, 16:35
Wohnort: Wien
Kontaktdaten:

Dienstag 30. September 2008, 13:22

Sandra hat geschrieben:Hi,

Ich bin im Grunde komplette Anfängerin was Programmieren und Python betrifft, daher hoffe ich, ihr könnt mir ein wenig helfen...

Wir haben die Aufgabe bekommen, eine Funktion zu schreiben, welche Daten sortieren kann.

Dazu habe ich auf Wikipedia (http://de.wikipedia.org/wiki/Python_(Pr ... ersprache)) diesen Code gefunden:

Code: Alles auswählen

def quicksort(liste):
    if len(liste) <= 1:
        return liste
    pivotelement = liste[0]
    links  = [element for element in liste[1:] if element <  pivotelement]
    rechts = [element for element in liste[1:] if element >= pivotelement]
    return quicksort(links) + [pivotelement] + quicksort(rechts)
doch was z.B.

Code: Alles auswählen

[element for element in liste[1:] if element <  pivotelement]
macht verstehe ich gar nicht. Was heißt element for element? oder [1:]?
Kann mir jemand in Worten die obigen Zeilen erklären?

mfg Sandra
Siehe http://docs.python.org/tut/node5.html#S ... 0000000000 und http://docs.python.org/tut/node7.html#S ... 0000000000
Ohloh | Mein Blog | Jabber: segfaulthunter@swissjabber.eu | asynchia – asynchrone Netzwerkbibliothek

In the beginning the Universe was created. This has made a lot of people very angry and has been widely regarded as a bad move.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Dienstag 30. September 2008, 13:29

Das erste ist eine list comprehension und abkürzende Schreibweise für eine normale for-Schleife. Das Python-Tutorial weiß mehr...

Das "[1:]" ist ein Teilliste, nämlich die vom Index 1 (bedenke, Python beginnt bei 0 zu zählen, also ist das Element mit dem Index 1 das zweite in der Liste) bis zum Ende (weil da nix steht). Siehe den Abschnitt über slices im Tutorial.

Allerdings: Wenn du eine Sortierfunktion schreiben -- und bestimmt auch erklären können -- sollst, würde ich nicht Quicksort empfehlen. Versuche dich lieber an einem einfacheren Algorithmus wie BubbleSort oder InsertionSort.

Stefan
Sandra
User
Beiträge: 11
Registriert: Dienstag 30. September 2008, 12:44

Dienstag 30. September 2008, 13:30

Hi,

Vielen Dank für die schnellen Antworten :)

Werde mal die Links durchlesen, und versuchen eine Funktion wie von numerix beschrieben zu erstellen.

mfg Sandra
sea-live
User
Beiträge: 440
Registriert: Montag 18. Februar 2008, 12:24
Wohnort: RP

Dienstag 30. September 2008, 14:01

um welche elemente handelt es sich in deiener Liste ziffern Namen Buchstaben oder kombinationen.
Python bietet da auch andere Funktionen liste.sort() oder sorted()

hier mal den wiki-beitrag dazu
http://wiki.python.org/moin/HowTo/Sorting
Sandra
User
Beiträge: 11
Registriert: Dienstag 30. September 2008, 12:44

Dienstag 30. September 2008, 14:27

Hi,

Habe es geschafft eine Funktion zu schreiben, welche eine Liste mit Zahlen sortiert:

Code: Alles auswählen

#! /usr/bin/env python

import random

a = []

for x in range(10):
  a.append(random.random())

a.append(-1)
a.append(-0.5)

print a

def sort1(li):
  a = []
  for x in range(len(li)):
    n = 0
    m = 0
    for y in range(len(li)):
      if li[y] > m:
        n = y
        m = li[y]
    a.append(li[n])
    del li[n]
  a.reverse()
  return a
  
b = sort1(a)  

print a
print b
Doch in a stehen danach nichts mehr, wie kann ich dies vermeiden?
Auch bei negativen Zahlen gibt es Probleme...

mfg Sandra
Darii
User
Beiträge: 1177
Registriert: Donnerstag 29. November 2007, 17:02

Dienstag 30. September 2008, 14:48

Sandra hat geschrieben:Doch in a stehen danach nichts mehr, wie kann ich dies vermeiden?
Das liegt daran, dass du die Liste auch mit del li[n] löscht, denn li und das a das du an die Funktion übergibst sind ein und dieselbe Liste. Dies behebst du indem du die Liste kopierst.

Code: Alles auswählen

def sort1(li):
    li = li[:]
    ...
Auch bei negativen Zahlen gibt es Probleme...
Du musst m mit einer negativen Zahl initialisieren.

Code: Alles auswählen

m = float("-inf")
Sandra
User
Beiträge: 11
Registriert: Dienstag 30. September 2008, 12:44

Dienstag 30. September 2008, 14:53

Perfekt, mit diesen Modifikationen funktioniert es :)

Vielen Dank nochmal an Alle :!:

mfg Sandra
sea-live
User
Beiträge: 440
Registriert: Montag 18. Februar 2008, 12:24
Wohnort: RP

Dienstag 30. September 2008, 18:12

dieses beispiel wäre mal wieder was für eine zeitanalyse !!

was läuft schneller !
beispiel

Code: Alles auswählen

#import random
#zahlen = [random.randint(0, 1023) for i in xrange(100)]
import time
zahlen = [788, 160, 822, 899, 98, 425, 959, 10, 173, 778,
        62, 729, 161, 208, 797, 276, 447, 540, 869, 657,
        76, 435, 418, 637, 728, 405, 243, 914, 9, 94, 1019,
        277, 225, 808, 66, 366, 529, 421, 112, 136, 895, 289,
        148, 669, 57, 871, 814, 183, 419, 915, 129, 294, 126,
        1000, 755, 109, 261, 161, 702, 9, 945, 332, 616, 427,
        238, 509, 316, 52, 563, 810, 163, 563, 364, 505, 629,
        870, 20, 755, 863, 405, 963, 51, 1014, 546, 431, 155,
        429, 499, 882, 598, 373, 445, 306, 390, 27, 856, 55,
        286, 813, 644]
t1 = time.clock()
za = sorted(zahlen)
t2 = time.clock()
print t2-t1
time = 8.24127088778e-005

Code: Alles auswählen

#import random
#zahlen = [random.randint(0, 1023) for i in xrange(100)]
import time
zahlen = [788, 160, 822, 899, 98, 425, 959, 10, 173, 778,
        62, 729, 161, 208, 797, 276, 447, 540, 869, 657,
        76, 435, 418, 637, 728, 405, 243, 914, 9, 94, 1019,
        277, 225, 808, 66, 366, 529, 421, 112, 136, 895, 289,
        148, 669, 57, 871, 814, 183, 419, 915, 129, 294, 126,
        1000, 755, 109, 261, 161, 702, 9, 945, 332, 616, 427,
        238, 509, 316, 52, 563, 810, 163, 563, 364, 505, 629,
        870, 20, 755, 863, 405, 963, 51, 1014, 546, 431, 155,
        429, 499, 882, 598, 373, 445, 306, 390, 27, 856, 55,
        286, 813, 644]
t1 = time.clock()
zahlen.sort()
t2 = time.clock()
print t2-t1
print zahlen
time = 7.06793740545e-005
BlackJack

Dienstag 30. September 2008, 18:32

Bei einem Zeitunterschied von 11 Microsekunden kann man nicht wirklich sagen welches für diese Daten schneller läuft.

Und das auf lange Sicht `sorted()` ein klein wenig langsamer ist, liegt auf der Hand, weil das zusätzlich eine Kopie der Liste anlegen muss.
Leonidas
Administrator
Beiträge: 16024
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Dienstag 30. September 2008, 18:39

Als Algorithmus wird in Python übringens das recht interessante Timsort verwendet (Tim steht für Tim Peters).
My god, it's full of CARs! | Leonidasvoice vs Modvoice
sea-live
User
Beiträge: 440
Registriert: Montag 18. Februar 2008, 12:24
Wohnort: RP

Dienstag 30. September 2008, 18:40

so jetzt manuell

Code: Alles auswählen

#import random
#zahlen = [random.randint(0, 1023) for i in xrange(100)]
import time
zahlen = [788, 160, 822, 899, 98, 425, 959, 10, 173, 778,
        62, 729, 161, 208, 797, 276, 447, 540, 869, 657,
        76, 435, 418, 637, 728, 405, 243, 914, 9, 94, 1019,
        277, 225, 808, 66, 366, 529, 421, 112, 136, 895, 289,
        148, 669, 57, 871, 814, 183, 419, 915, 129, 294, 126,
        1000, 755, 109, 261, 161, 702, 9, 945, 332, 616, 427,
        238, 509, 316, 52, 563, 810, 163, 563, 364, 505, 629,
        870, 20, 755, 863, 405, 963, 51, 1014, 546, 431, 155,
        429, 499, 882, 598, 373, 445, 306, 390, 27, 856, 55,
        286, 813, 644]
def sort1(li):
  li = li[:]
  for x in range(len(li)):
    for y in range(len(li)-1):
      if li[y+1] < li[y]:
          tmp =  li[y]
          li[y] = li[y+1]
          li[y+1] =tmp
  return li

t1 = time.clock()
za = sort1(zahlen)
t2 = time.clock()
print t2-t1
print za
time = 0.00698384850589
Benutzeravatar
Craven
User
Beiträge: 223
Registriert: Dienstag 24. Januar 2006, 13:37

Dienstag 30. September 2008, 18:51

sea-live hat geschrieben:

Code: Alles auswählen

          tmp =  li[y]
          li[y] = li[y+1]
          li[y+1] =tmp
Das Vertauschen geht so "einfacher":

Code: Alles auswählen

>>> a = 1
>>> b = 0
>>> a, b = b, a
>>> a, b
(0, 1)
[code]q = 'q = %s; print q %% repr(q)'; print q % repr(q) [/code]
sea-live
User
Beiträge: 440
Registriert: Montag 18. Februar 2008, 12:24
Wohnort: RP

Dienstag 30. September 2008, 18:59

das ist bei mir aber langsammer ?
selber testen

Code: Alles auswählen

#import random
#zahlen = [random.randint(0, 1023) for i in xrange(100)]
import time
zahlen = [788, 160, 822, 899, 98, 425, 959, 10, 173, 778,
        62, 729, 161, 208, 797, 276, 447, 540, 869, 657,
        76, 435, 418, 637, 728, 405, 243, 914, 9, 94, 1019,
        277, 225, 808, 66, 366, 529, 421, 112, 136, 895, 289,
        148, 669, 57, 871, 814, 183, 419, 915, 129, 294, 126,
        1000, 755, 109, 261, 161, 702, 9, 945, 332, 616, 427,
        238, 509, 316, 52, 563, 810, 163, 563, 364, 505, 629,
        870, 20, 755, 863, 405, 963, 51, 1014, 546, 431, 155,
        429, 499, 882, 598, 373, 445, 306, 390, 27, 856, 55,
        286, 813, 644]
def sort(li):
    return li.sort()

def sortet(li):
    return sorted(li)
    
def sort1(li):
  for x in range(len(li)):
    for y in range(len(li)-1):
      if li[y+1] < li[y]:
          tmp =  li[y]
          li[y] = li[y+1]
          li[y+1] =tmp
  return li
def tauschen(li):
  for x in range(len(li)):
    for y in range(len(li)-1):
      if li[y+1] < li[y]:
          li[y+1],li[y] = li[y],li[y+1]
  return li
    
t1 = time.clock()
za = sort(zahlen)
t2 = time.clock()
print 'sort'
print t2-t1
#print za
t1 = time.clock()
za = sortet(zahlen)
t2 = time.clock()
print 'sorted'
print t2-t1
#print za
t1 = time.clock()
za = sort1(zahlen)
t2 = time.clock()
print 'forschleife'
print t2-t1
#print za

t1 = time.clock()
za = tauschen(zahlen)
t2 = time.clock()
print 'tauschen'
print t2-t1
#print za




ergebniss
sort
7.29142949732e-005
sorted
4.10666718815e-005
forschleife
0.00497465459996
tauschen
0.00504365778332
FEHLERTEUFEL
die nachfolgenden funktionen bekommen ja ein sortiertes nicht ein unsortiertes array(liste)
Antworten