Quicksort Algorithmus

[Thunderskull]

Den Titel in wie fern ändern

 

[aveiro messiah]

Deviant sind noch 2 Fehler drin, ich weis nicht wie ich die klammern anders setzen soll. hab jetzt saemmtliche varianten probiert.

16 C:\Dev-Cpp\Quicksort2.cpp expected init-declarator before "if"
16 C:\Dev-Cpp\Quicksort2.cpp expected `,' or `;' before "if"

44 C:\Dev-Cpp\Quicksort2.cpp expected primary-expression before "int"
44 C:\Dev-Cpp\Quicksort2.cpp expected `;' before "int"

 

[.deviant]

Der Quellcode ist nicht von mir Und äh hab auch grad keine Zeit mich reinzudenken, bzw keinen Compiler grad am PC, musst du auf Liontiger warten

 

[sHiRoKKo]

Beim Visual Studio 2008 bekomme ich die Fehler ganz einfach weg indem ich in der ersten Zeile noch die stdafx.h include, also:

#include "stdafx.h"
#include <iostream>
#include <string>

usw.

 

[aveiro messiah]

hm, habe dev-C++!!

 

[Liontiger]

womit kompilierst du denn aveiro messiah?^^ habs mit g++ und mit Visual Studio probiert und bei mir gehts einwandfrei

edit: zu spät

 

[aveiro messiah]

mit dev - c++ !

 

[Liontiger]

habs gerade auch mal in dev-c++ ausprobiert und auch da klappts bei mir o0

siehe Kompilier Log unten:

btw.: du kannst es ja wenn du ne Version von deinem QuickSort Algorithmus hast die du kompilieren kannst auch gerne selber probieren vielwas muss man gar nicht ändern, um mit Strings zu arbeiten musst du eben noch <string> includen - und was evtl. noch wichtig/interessant ist, ist dass du Strings auch mit normalen Vergleichsoperatoren vergleichen kannst, also am eigentlichen Algorithmus musst du gar nichts ändern, im Prinzip sinds nur ein paar Datentypen die du ersetzen musst

 

[aveiro messiah]

funktioniert super geil, kannst mir ne art struktur noch machen dazu, das ich das evtl noch bisserl besser kapiere ?

 

[Liontiger]

gibts ein bestimmtes Problem irgendwo in der implementierung? oder gehts allgemein um den algorithmus?^^ du meintest ja im ersten post das du das Prinzip schon verstanden hast
wenn's nen allgemeines Problem mit dem Algorithmus gibt dann würd ich dir empfehlen z.B. auf Wikipedia nachzulesen, besser erklären werd ichs auch nicht können vermute ich mal wenns was spezielles oder irgendwas im Code geht dann bitte ein wenig genauer sagen wo das Problem liegt ^^

 

[aveiro messiah]

Ok perfect hab alles hinbekomen big thx liontiger... bekommst es noch hin mir da was einzuhauen das er duplikate löscht also quasi wenn doppelte namen reinkommen... die rausschmeißen? er soll auch via schleife suchen... ich weis nicht wo ich die machen soll!

 

[sHiRoKKo]

Eine Möglichkeit wäre sich das 1. Element zu merken und dann in einer Schleife alle anderen Elemente durchzugehen und mit dem gemerkten zu vergleichen + entfernen, wenn nötig. Das gleiche macht man dann mit dem 2. Element, dem 3. usw. bis man beim letzten angekommen ist.

Das wäre jetzt das was mir einfällt, gibt aber bestimmt noch andere Möglichkeiten.

 

[Liontiger]

leider is die sache mit dem entfernen aus nem array ein wenig problematisch weil das array zunächst mal eine feste größe hat
da wären andere datenstrukturen deutlich angenehmer für ^^ überlege mir evtl. später noch was, bin grad erst nach haus gekommen, erstmal ein paar andere sachen noch erledigen dann mal schauen

€dit: sry, heut nich mehr hab zu viel andern kram gehabt - aber als ansatz kannst du sHiRoKKos vorschlag ja schon nehmen - entfernen kannst du die elemente zwar nicht direkt aber du kannst zählen wieviele duplikate, bzw. voneinander unterscheidbare Elemente in deinem Array sind. Dann erstellst du dir ein Array der Größe die es nachher ohne Duplikate haben will und fügst die Elemente aus dem Ursprungsarray da ein, allerdings eben ohne die Duplikate - schaust halt für jedes Element obs schon drin ist und falls ja nimmste das nächste.

ansonsten warten oô vllt. morgen^^ aber prinzip sollte ja klar sein 0o

 

[Liontiger]

soo hab mal was gemacht, bitte prügelt nich auf mich ein ich weiß, die implementierung is alles andere als optimal aber wenigstens funktionierts
wichtig auch, voraussetzung dafür, dass das hier funktioniert, ist das die elemente sortiert sind, aber soweit ich das verstanden hab sollte das ja ne Art Erweiterung für das letzte sein, dann sollte das ja nicht das Problem sein

#include <iostream>
#include <string>

using namespace std;
void quicksort(string *a, int left, int right) 
{
  if (left < right) 
  {
    string pivot = a[right];
    int l = left;
    int r = right;
    do 
	{
	  while (a[l] < pivot) 
	    l++;
      while (a[r] > pivot)
	    r--;

      if (l <= r) 
	  {
        string swap = a[l];
        a[l] = a[r];
        a[r] = swap;
        l++;
        r--;
      }
    } while (l <= r);

    quicksort(a, left, r);
    quicksort(a, l, right);
  }
}

/* 
   Überprüft ob ein String der im Parameter mit geliefert wird in einem Array 
   von ebenfalls gegebener Größe schon vorhanden ist. 
   Gibt Wert vom typ bool (true/false) zurück.
*/
bool isStringInArray(string* array, string element,int count)
{
  for (int i = 0; i < count; i++)
  { 
      if ( element.compare(array[i]) == 0 )
         return true;
  }
  return false;
}

/*
  Vergleicht über die Länge eines Arrays jeweils das aktuelle Element mit seinem 
  Nachfolger und erhöht einen Zähler, sofern die Elemente gleich sind. 
  Da jeweils nur aufeinanderfolgende Elemente verglichen werden müssen die 
  Elemente im Array sortiert sein.
*/
int getDuplicateCount(string* a, int count)
{
  int duplicateCount = 0;

  for (int i = 0; i < count-1; i++)
  {
      if (a[i] == a[i+1])
          {
               duplicateCount++;
          }
  }
  return duplicateCount;
}

int main() 
{
  string values[] = {"klaus", "philipp", "hans", "sarah", "sarah", "franz", "franz", "julia", "hans", "sarah", "zeus", "jessica", "peter"};
  int count = sizeof(values) / sizeof(*values);

  for (int i = 0; i < count; i++) 
    cout << values[i] << " ";
  cout << endl;

  quicksort(values, 0, count - 1);

  for (int i = 0; i < count; i++) 
    cout << values[i] << " ";
  cout << endl;

  //Anzahl der nicht Duplikate ist = Anzahl der Elemente - Duplikatanzahl
  int nonDuplicates = count - getDuplicateCount(values,count);
  
  /*Neues Array erstellen in dem die Werte ohne die Duplikate eingetragen
  werden können*/
  string newArray[nonDuplicates];
  
  /*
   Für jedes Element im Ausgangsarray prüfen ob das Element schon im neuen
   Array ist - falls ja, zum nächsten Schleifendurchlauf springen, falls nein
   das Element ins neue Array einfügen
  */ 
  for (int i = 0,j = 0; i < count; i++)
  {
    if (isStringInArray(newArray, values[i], nonDuplicates))
       continue;
    else 
       newArray[j++] = values[i];
  }
  
  cout << endl << "Ohne Duplikate: "<<endl;
  //neues Array ohne die Duplikate ausgeben
  for (int i = 0; i < nonDuplicates; i++) 
    cout << newArray[i] << " ";

  cout << endl;

  system("PAUSE");
  return 0;
}

 

[Thunderskull]

was gehtn hier? oo den Fred hab ich aber ned erstellt ^^ Bug Bug Buuuuuuuuuuuuuuugs XD

 

[Liontiger]

http://74.125.39.104/search?q=cache...echnik-ecke-f544/quicksort-algorithmus-74782/

da gibts noch den originalthread ^^

 

[aveiro messiah]

boha super geil alter besten dank man

 

[Liontiger]

bitte bitte
grausam zu sehen wie wenig aber von den c++ kenntnissen ausm ersten semester hängen geblieben is da hakts dann schon wenn man die länge von nem array bestimmen will , java machts einem viel zu einfach so'n kleinkram müsste man echt besser hinbekommen denk ich^^
aber so vergess ich wenigstens nich alles