Arrays & Sotieralgorythmen !

Frage zu Introsort - wie funktioniert der? Hat nicht Mergesort auch worst case O(nlogn) und ist trotzdem im schnitt langsamer als Quicksort?
 

So, hab da nochma ne frage! :rolleyes:

Wie sotier ich denn am besten ein Array wo nur AnsiString's drinne sind ?
Da blick ich mom garnich durch ! :eek:
THX schon mal im vorraus !
 
Original geschrieben von Kachelator
Was meinst du damit? Kannst du mal was Code zeigen?
Zum Vergrößern anklicken....

Nein kann ich leider nich... deswegen frag ich ja gerade! :confused:
ein beispiel wäre eine z.B. ein Lager mit 5 aktikeln im array

| Artikl Name | Art nr. | Warengruppe | Anzahl | Preis |
--------------------------------------------------------------------------------------
| Schrauben | 1245 | Wekzeug | 10 Päckchen | 1,35 € Stk. |
| Hammer | 1276 | Wekzeug | 6 Päckchen | 1,15 € Stk. |
| Bohrer | 1357 | Wekzeug | 3 Päckchen | 1,00 € Stk. |
| Dübel | 2896 | Wekzeug | 10 Päckchen | 1,95 € Stk. |
| Nägel | 7096 | Wekzeug | 2 Päckchen | 2,35 € Stk. |
--------------------------------------------------------------------------------------

wenn ich dieses alphabethisch nach dem artikelnamen sortieren will !
 
Wenn du jede der fünf Zeilen in einen std::string packst und die alle in einen std::vector<std::string>, dann kannst du da direkt std::sort() drüberlaufen lassen.
Ich vermute aber, dass du ohnehin eine Klasse für deine Artikel bauen solltest und dadurch auch besseren Zugriff auf die zusätzlichen Informationen wie den Preis bekommst. Ich habe dir hier mal was programmiert -- nicht erschrecken:
Code: 
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>


class artikel
{
public:
  std::string name_;
  int         nummer_;
  std::string gruppe_;
  int         anzahl_;
  float       preis_;
  
  //- praktischer Konstruktor:
  artikel( const std::string& name, 
           int nummer,
           const std::string& gruppe,
           int anzahl,
           float preis )
  : name_( name ), nummer_( nummer ), gruppe_( gruppe ), anzahl_( anzahl ), preis_( preis )
  {}

  //- praktisch für Ausgabe: <<-Operator
  friend std::ostream& operator <<(  std::ostream& of, const artikel& a );
  
  // Vergleichoperator für Sortierung nach name_;
  friend struct vergleiche_name;
  // Vergleichoperator für Sortierung nach nummer_;
  friend struct vergleiche_nummer;
};

std::ostream& operator <<(  std::ostream& of, const artikel& a )
{
  of  << a.name_   << ", " 
      << a.nummer_ << ", " 
      << a.gruppe_ << ", " 
      << a.anzahl_ << ", " 
      << a.preis_  << std::endl;
  return of;
}

// Zwei Funktoren als Vergleichsoperatoren:
struct vergleiche_name
{
  bool operator()( const artikel& lhs, const artikel& rhs ) const
  {
    return lhs.name_ < rhs.name_;
  }
};

struct vergleiche_nummer
{
  bool operator()( const artikel& lhs, const artikel& rhs ) const
  {
    return lhs.nummer_ < rhs.nummer_;
  }
};

// dasselbe als Funktionen:
bool vergleiche_name_func( const artikel& lhs, const artikel& rhs )
{
  return lhs.name_ < rhs.name_;
}

bool vergleiche_nummer_func( const artikel& lhs, const artikel& rhs )
{
  return lhs.nummer_ < rhs.nummer_;
}



int main(int argc, char* argv[])
{
  typedef std::vector< artikel > artikel_container_typ; 
  artikel_container_typ lager;
  lager.reserve( 5 ); // platz reservieren
  
  // lager füllen
  lager.push_back( artikel( "Schrauben", 1245, "Wekzeug [sic!]", 10, 1.35f ) );  
  lager.push_back( artikel( "Hammer",    1276, "Wekzeug [sic!]", 6,  1.15f ) );  
  lager.push_back( artikel( "Bohrer",    1357, "Wekzeug [sic!]", 3,  1.00f ) );  
  lager.push_back( artikel( "Dübel",     2896, "Wekzeug [sic!]", 10, 1.96f ) );  
  lager.push_back( artikel( "Nägel",     7096, "Wekzeug [sic!]", 2,  2.35f ) );  
  
  // ausgeben
  std::cout << "*** Lager: ********" << std::endl;
  std::copy( lager.begin(), lager.end(), std::ostream_iterator<artikel>( std::cout ) ); 

  // sortieren nach name mit Funktor
  std::sort( lager.begin(), lager.end(), vergleiche_name() ); 
  // // sortieren nach name mit Funktion
  // std::sort( lager.begin(), lager.end(), vergleiche_name_func ); 
  
  // ausgeben
  std::cout << "*** Lager nach name: ********" << std::endl;
  std::copy( lager.begin(), lager.end(), std::ostream_iterator<artikel>( std::cout ) ); 

  // sortieren nach name mit Funktor
  std::sort( lager.begin(), lager.end(), vergleiche_nummer() ); 
  // // sortieren nach name mit Funktor
  // std::sort( lager.begin(), lager.end(), vergleiche_nummer_func ); 
  
  // ausgeben
  std::cout << "*** Lager nach nummer: ********" << std::endl;
  std::copy( lager.begin(), lager.end(), std::ostream_iterator<artikel>( std::cout ) ); 

  char c;
  std::cin >> c;
  return 0;
}
Spiel mal damit rum und frag nach, wenn du etwas nicht verstehst. Es läuft mit Visual C++ 6.
 
Original geschrieben von Matthias Reitinger
@sqeaker: Wie wäre es denn mal mit einem Tutorial über eine kleine Auswahl von Sortieralgorithmen, du scheinst da recht firm zu sein :)
Zum Vergrößern anklicken....

OK - wird wie die Datenkompression in pdf gegossen.

BTW - ich hab irgendwo gestern im Zuge meiner recherche eine Seite gefunden, die Tatsächlich herausgefunden hat, dass ein ordentlich für den Prozessor optimierter heap sort schneller als quicksort ist. Was sehr praktisch wäre, da heap worst case O(n log n) hat während Quicksort worst case nur O(n^2) hat.
Im Mittel sind beide die gleiche Klasse, aber normalerweise ist Quicksort schneller.

P.S.:
Der erste Sortieralgorithmus im Tut wird Tobi-Sort sein - ein von mir in der Praktische Informatik II entwickelter Algorithmus. Er funktioniert recht einfach:

Man bildet eine zufällige Permutation der Daten und überprüft danach ob sie sortiert ist. Einfach zu implementieren.

Worst Case Laufzeit: unendlich (tritt nur mit unendlich kleiern Wahrscheinlichkeit ein, ist also aktzeptabel ;-)
Speicher: O(2n) bzw. dürfte auch in O(n) gehen.

Das Gesetz der großen Zahlen garantiert, dass die Wahrscheinlichkeit, dass der Algorithmus terminiert gegen 1 geht.
 
Zuletzt bearbeitet:
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück