Hilfe bei QuickSort

Guten Tag,
Habe folgendes Problem, ich möchte ein quicksort Programm schreiben und habe dafür ein feld int zahlen[]={5,22,8,16,55,7,99,12,9,};
Von rechts wird begonnen (zahl=9) und eine Element gesucht, dass kleiner oder gleich dem Trennelement ist (Zahl in der Mitte =55).
Von links (zahl=5) wird ein Element gesucht, dass größer oder gleich dem Trennelement ist.Diese Elemente werden getauscht.Falls sich der ober und der untere Zeiger kreuzen, wird an dieser Stelle die Reihung in zwei neue Teilfelder geteilt.
(Im unteren Teilfeld sind nun alle Elemente, die kleiner oder gleich dem Trennelement sind. Im oberen Teilfeld sind diejenigen, die größer oder gleich dem Trennelement sind). So, jetzt habe ich allerdings das Problem das ich nicht weiss wie ich in dem Feld die Zahlen tausche oder vergleiche
kann mir bitte jemand helfen?
Vielen Dank

CodeFinder

Also der Zugriff auf ein Array erfolg so:
Array[Position] = Wert;
also Beispiel:

zahlen[0] = 1; // statt 5 ist jetzt die 1 die erste Zahl im Array

Der Vergleich ist eigntl. das selbe:
Beispiel:

if(zahlen[0] == zahlen[8])
{// trifft nicht zu!
}
else
{// trifft -nach deinen Zahlenwerten- zu!
}

Das Tauschen geht so:

// 1. Wert mit letztem tauschen:
int iTemp;
iTemp = zahlen[0];
zahlen[0] = zahlen[8];
zahlen[8] = iTemp;

PS_1: Wenns dir nur darum geht die Zahlen zu sortieren (mit QuickSort), dann guck dir mal die C-Funktion qsort() an.

PS_2: Das erste Element hat immer den Index 0 (s.g. 0-Index), das letzte Anzahl -1!

Jester

CodeFinder schrieb:

PS_1: Wenns dir nur darum geht die Zahlen zu sortieren (mit QuickSort), dann guck dir mal die C-Funktion qsort() an.

Da wir hier im C++-Forum sind bitte lieber std::sort aus <algorithm> anschaun.

Hi danke für die schnelle Antworten, ich habe das ganze jetzt mal versucht so weit zu Programmieren das links die Zahlen stehen die kleiner sind als die Zahl in der Mitte(55) un recht die höheren, aber irgendwie hab ich mist gebaut und komm nicht so recht drauf hier ist mal mein code

int z=8,x=0;
 while(z>=4)
 {

 if(zahlen[4] > zahlen[z])
  {
   while(x<=4)
   if(zahlen[4] < zahlen[x])
   {
    int iTemp;
    iTemp = zahlen[z];
    zahlen[z] = zahlen[x];
    zahlen[x] = iTemp;
   }
   else  x++;
  }
  else z--;
 }

ich bin schlecht ich weiss^^
aber könnt ihr mir bitte helfen?

Bitte helft mir^^

MFK

Versuch dich doch erst mal an einem Bubblesort, das dürfte vom Schwierigkeitsgrad her angemessener sein.

Jo werd ich machen, aber eigentlich würd ich das hier auch gerne fertig bekommen

CStoll

Vor allem solltest du die Obergrenze z nicht mit dem Mittelpunkt des Arrays vergleichen, sondern mit der Untergrenze x (wenn das mittlere Element nicht gerade der Median ist, bekommst du sonst leichte Probleme

PS: Ein Blick in die Wikipedia hilft auch weiter: QuickSort, Sortieren

MFK

ThunderDragon schrieb:

Jo werd ich machen, aber eigentlich würd ich das hier auch gerne fertig bekommen

Wirst du ja auch. Ich habe ja nicht gesagt, dass du nach dem Bubblesort aufhören sollst

Hi, hab jetzt doch mal weiter gemacht^^.(hab bubblesort schonmal in der Schule gemacht) und es sortiert jetzt auch schon die Zahlen, die kleiner sind als die Vergleichszahl nach links und die die größer sind nach rechts. Allerdings geht die rekursion nicht ... hab da irgendwie was falsch gemacht, kann sich das mal bitte einer anschaun? steh aufm schlauch

#include<iostream>
using namespace std;

void quicksort(int anfang=0,ende=7)
{
int sort[]={2,1,3,6,5,7,8,4}, links=z,rechts=z1;
int vergleichselement=4;
for(int i=0;i<8;i++)cout<<sort[i]<<", ";
cout<<endl;
do
{
  while(sort[links]<sort[vergleichselement])
   links=links+1;
  while(sort[rechts]>sort[vergleichselement])
   rechts=rechts-1;
  if(links<=rechts)
   {
    int tausch=sort[links];
    sort[links]=sort[rechts];
    sort[rechts]=tausch;
    links=links+1;
    rechts=rechts-1;
   }
}while(rechts<links);

if(0<rechts)
   quicksort(anfang,rechts)
if(links<7)
   quicksort(links,ende)

for(int i=0;i<8;i++)cout<<sort[i]<<", ";
cin.get();
}

komm irgendwie nicht drauf
Es kommt immer die meldung Größe von 'quicksort' unbekannt oder null, kann damit abe rnichts anfangen. und fehler in der deklarationssyntax hier

void quicksort(int anfang=0,ende=7)
{

MFK

Du musst schon dazu schreiben, welchen Typ ende hat. Außerdem kann deine Rekursion nicht funktionieren, weil du auf jeder Ebene das Array wieder neu anlegst. Das Array muss außerhalb der Funktion liegen. Zu guter Letzt wäre es wohl auch noch gut, wenn du anfang und ende innerhalb der Funktion auch zum Sortieren benutzen würdest, nicht nur für die Rekursion.