Sortieralgorithmus - Problem

[Sandra]

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

[numerix]

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.

[name]

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

[sma]

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]

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]

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]

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]

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]

Perfekt, mit diesen Modifikationen funktioniert es

Vielen Dank nochmal an Alle

mfg Sandra

[sea-live]

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]

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]

Als Algorithmus wird in Python übringens das recht interessante Timsort verwendet (Tim steht für Tim Peters).

[sea-live]

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

[Craven]

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)

[sea-live]

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)

[BlackJack]

@sea-live: Die Zahlen sind IMHO nicht aussagekräftig, da viel zu klein. Bei der kurzen Laufzeit und den wenigen Daten fallen Laufzeitschwankungen viel zu sehr ins Gewicht.

[sea-live]

Danke für die info

war sowieso grade beim Basic an dem sortieren deswegen der versuch hier mal in python
mit 4Mhz würde das dann was ausmachen
tauschen bubbel sort oder quicksort

[name]

das ist bei mir aber langsammer ?
selber testen

Code: Alles auswählen

....

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)

Du solltest, wenn du schon timings machst, zumindestens xrange benutzen. Ausserdem koennte man die timings schoen in eine Funktion auslagern, aber das ist hier nicht das Thema.

[BlackJack]

@Sandra: Das `x` aus der äusseren Schleife wird nicht verwendet. Das könnte man auch einfacher mit einer ``while``-Schleife formulieren.

`range()` erzeugt eine Liste mit Zahlen die eigentlich gar nicht gebraucht wird. `xrange()` ist da speicherschonender.

Schau Dir mal die `pop()`-Methode auf Listen an.

Und ``m = float("-inf")`` ist keine so gute Idee, da es erstens so nicht auf jeder Plattform funktioniert, denn die Zeichenkettendarstellung für Unendlich hängt von der C-Bibliothek ab. Unter Windows sieht das z.B. anders aus. Und zweitens muss "Minus Unendlich" nicht für jeden Datentyp der kleinste Wert sein. Man sollte hier vielleicht besser aus den Daten einfach das Minimum bestimmen. Oder das Maximum und dann die Bedingung in Zeile 21 umdrehen. Damit wird das `reverse()` überflüssig.

[Sandra]

Das `x` aus der äusseren Schleife wird nicht verwendet. Das könnte man auch einfacher mit einer ``while``-Schleife formulieren.

Dies vestehe ich nicht ganz, wie lässt sich denn eine while-Schleife dafür einsetzen?

`range()` erzeugt eine Liste mit Zahlen die eigentlich gar nicht gebraucht wird. `xrange()` ist da speicherschonender.

OK werde ich mir merken.

Schau Dir mal die `pop()`-Methode auf Listen an.

Ich nehme an, du meinst etwas wie:

Code: Alles auswählen

a.append(li.pop(n))

Und ``m = float("-inf")`` ist keine so gute Idee, da es erstens so nicht auf jeder Plattform funktioniert, denn die Zeichenkettendarstellung für Unendlich hängt von der C-Bibliothek ab. Unter Windows sieht das z.B. anders aus. Und zweitens muss "Minus Unendlich" nicht für jeden Datentyp der kleinste Wert sein. Man sollte hier vielleicht besser aus den Daten einfach das Minimum bestimmen. Oder das Maximum und dann die Bedingung in Zeile 21 umdrehen. Damit wird das `reverse()` überflüssig.

Wie kann man denn das Minimum ermitteln, dieses verändert sich ja, bei

Code: Alles auswählen

a.append(li.pop(li.index(min(li))))

würde doch sicherlich 2 mal die Liste durchgegangen, oder?

mfg Sandra