QuickSort absteigend

Übersicht

BlitzBasic

Allgemein

	bmurray Betreff: QuickSort absteigend	Mi, Jan 07, 2015 18:06 Antworten mit Zitat
Liebe Gemeinde, leider habe ich es trotz etlicher Versuche nicht hinbekommen, den QuickSort-Algorithmus absteigend sortieren zu lassen. Dabei habe ich den Pseudocode von der Wiki-Seite genommen. In Basic sieht der dann so aus: Code: [AUSKLAPPEN] [EINKLAPPEN] Function quicksort(links,rechts) Local teiler If links < rechts Then teiler = teile(links,rechts) quicksort(links,teiler-1) quicksort(teiler+1,rechts) End If End Function Function teile(links,rechts) Local i,j Local pivot Local temp i = links j = rechts - 1 pivot = werte(rechts) While i < j While werte(i) <= pivot And i < rechts i = i + 1 Wend While werte(j) >= pivot And j > links j = j - 1 Wend If i < j Then temp = werte(i) werte(i) = werte(j) werte(j) = temp End If Wend If werte(i) > pivot Then temp = werte(i) werte(i) = werte(rechts) werte(rechts) = temp End If Return i End Function Gestartet wird der Algorithmus dann mit Code: [AUSKLAPPEN] [EINKLAPPEN] quicksort(0,20) Die Liste ist im Array werte(20) gespeichert. Kann mir jemand sagen, welche Änderungen übernommen werden müssen, damit der absteigend sortiert?

bmurray

Betreff: QuickSort absteigend

Mi, Jan 07, 2015 18:06
Antworten mit Zitat

Liebe Gemeinde,

leider habe ich es trotz etlicher Versuche nicht hinbekommen, den QuickSort-Algorithmus absteigend sortieren zu lassen. Dabei habe ich den Pseudocode von der Wiki-Seite genommen.

In Basic sieht der dann so aus:

Code: [AUSKLAPPEN]

Function quicksort(links,rechts)
Local teiler
If links < rechts Then
   teiler = teile(links,rechts)
   quicksort(links,teiler-1)
   quicksort(teiler+1,rechts)
End If
End Function

Function teile(links,rechts)
Local i,j
Local pivot
Local temp

i = links
j = rechts - 1
pivot = werte(rechts)

While i < j
   While werte(i) <= pivot And i < rechts
      i = i + 1
   Wend
   While werte(j) >= pivot And j > links
      j = j - 1
   Wend
   If i < j Then
      temp = werte(i)
      werte(i) = werte(j)
      werte(j) = temp
   End If
Wend

If werte(i) > pivot Then
   temp = werte(i)
   werte(i) = werte(rechts)
   werte(rechts) = temp
End If

Return i
End Function

Gestartet wird der Algorithmus dann mit

Code: [AUSKLAPPEN]

quicksort(0,20)

Die Liste ist im Array werte(20) gespeichert.

Kann mir jemand sagen, welche Änderungen übernommen werden müssen, damit der absteigend sortiert?

	DAK	Do, Jan 08, 2015 1:32 Antworten mit Zitat
Einfach überall rechts und lins vertauschen. Wenn die Funktion nach links aufsteigt, dann ist es gleichbedeutend damit, dass sie nach rechts absteigt. Seiten vertauschen und alles rennt.
Gewinner der 6. und der 68. BlitzCodeCompo

DAK

Do, Jan 08, 2015 1:32
Antworten mit Zitat

Einfach überall rechts und lins vertauschen. Wenn die Funktion nach links aufsteigt, dann ist es gleichbedeutend damit, dass sie nach rechts absteigt. Seiten vertauschen und alles rennt.

Gewinner der 6. und der 68. BlitzCodeCompo

	bmurray	Do, Jan 08, 2015 13:31 Antworten mit Zitat
@DAK Hat leider nicht geklappt. Sortiert immer noch aufsteigend

bmurray

Do, Jan 08, 2015 13:31
Antworten mit Zitat

@DAK

Hat leider nicht geklappt. Sortiert immer noch aufsteigend Sad

	BladeRunner Moderator	Do, Jan 08, 2015 18:41 Antworten mit Zitat
Dann wird es ohne einen Blick in deinen aktuellen Code schwierig.
Zu Diensten, Bürger. Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92

BladeRunner

Moderator

Do, Jan 08, 2015 18:41
Antworten mit Zitat

Dann wird es ohne einen Blick in deinen aktuellen Code schwierig.

Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

	bmurray	Do, Jan 08, 2015 19:54 Antworten mit Zitat
lieber wieder gelöscht

bmurray

Do, Jan 08, 2015 19:54
Antworten mit Zitat

lieber wieder gelöscht Embarassed

Zuletzt bearbeitet von bmurray am Do, Jan 08, 2015 20:30, insgesamt einmal bearbeitet

	DAK	Do, Jan 08, 2015 20:09 Antworten mit Zitat
Toll, du hast ernsthaft überall die Worte Links und Rechts vertauscht, nicht aber deren Bedeutung! Im Grunde hast du jetzt einfach dem Programm gesagt, dass Rechts jetzt "Links" heißt und umgekehrt. Hier mal die Minimallösung: BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] Function quicksort(links,rechts) Local teiler If links < rechts Then teiler = teile(links,rechts) quicksort(links,teiler-1) quicksort(teiler+1,rechts) End If End Function Function teile(links,rechts) Local i,j Local pivot Local temp i = links j = rechts - 1 pivot = werte(rechts) While i < j While werte(i) >= pivot And i < rechts i = i + 1 Wend While werte(j) <= pivot And j > links j = j - 1 Wend If i < j Then temp = werte(i) werte(i) = werte(j) werte(j) = temp End If Wend If werte(i) < pivot Then temp = werte(i) werte(i) = werte(rechts) werte(rechts) = temp End If Return i End Function Unterschiede: Die Swap-Condition ist einfach Vorzeichenumgekehrt. Geht eigentlich ganz einfach aus der Beschreibung des Algos auf Wiki raus.
Gewinner der 6. und der 68. BlitzCodeCompo

DAK

Do, Jan 08, 2015 20:09
Antworten mit Zitat

Toll, du hast ernsthaft überall die Worte Links und Rechts vertauscht, nicht aber deren Bedeutung!

Im Grunde hast du jetzt einfach dem Programm gesagt, dass Rechts jetzt "Links" heißt und umgekehrt.

Hier mal die Minimallösung:

BlitzBasic: [AUSKLAPPEN]

Function quicksort(links,rechts) 
   Local teiler 
   If links < rechts Then 
      teiler = teile(links,rechts) 
      quicksort(links,teiler-1) 
      quicksort(teiler+1,rechts) 
   End If 
End Function 
    
Function teile(links,rechts) 
   Local i,j 
   Local pivot 
   Local temp 
    
   i = links 
   j = rechts - 1 
   pivot = werte(rechts) 
    
   While i < j 
      While werte(i) >= pivot And i < rechts 
         i = i + 1 
      Wend 
      While werte(j) <= pivot And j > links 
         j = j - 1 
      Wend 
      If i < j Then 
         temp = werte(i) 
         werte(i) = werte(j) 
         werte(j) = temp 
      End If 
   Wend 
    
   If werte(i) < pivot Then 
      temp = werte(i) 
      werte(i) = werte(rechts) 
      werte(rechts) = temp 
   End If 
    
   Return i 
End Function