(C) Seltsame Sortierung

[Markus Trusk]

Hi,
ich hoffe meine Frage sprengt nicht all zu sehr den Rahmen des Forums, aber hätte eine Frage zur C Sortierung. Ich habe versucht eine kleine Namenssortierung zu programmieren, aber das Programm gibt mir die Namen nur irgendwie aus, und nicht der Reihe nach sortiert. Was genau heißt es eigentlich, wenn ein String "größer" oder "kleiner" als der andere ist? In meinem C Buch steht das zB bei strcmp dabei: < 0 bedeutet str1 ist kleiner als str2. Ist hier die Länge gemeint oder wie? Selbst wenn, werden die Namen im Programm trotzdme nur irgendwie sortiert.
Hier das Programm:

#include <iostream.h>
#include <conio.h>
#include <string.h>

#define AZ 5 /*Anzahl der Namen, die eingegeben werden können */
#define LA 15 /*Länge der Namen */

typedef char namen[AZ][LA];

void nameneinlesen(namen &einlesestrings)    {
     int i;
           for (i = 0; i < AZ; i++)    {
           cout << "Gib den Namen " << (i + 1) << "ein: ";
           cin >> einlesestrings[i];
           }
     }
     void namensausgabe(namen ausgabestrings)    {
     int i;
     cout <<"Sortierte Ausgabe:\n";
           for (i = 0; i < AZ; i++)    {
           cout <<ausgabestrings[i] <<"\n";
           }
     }
     void sortieren(namen &einlesestrings)    {
     char temp[LA];
     int i;

for (i = 0; i < AZ; i++)    {
                  if (strcmp(einlesestrings[i], einlesestrings[i+1]) < 0)    {
                  strcpy(temp, einlesestrings[i+1]);
                  strcpy(einlesestrings[i+1], einlesestrings[i]);
                  strcpy(einlesestrings[i], temp);
                  }
            }
     }

void main()    {
     namen namenstring;
     nameneinlesen(namenstring);
     sortieren(namenstring);
     namensausgabe(namenstring);

}

Markus Trusk.

[Christian Kruse]

Hallo Markus,

ich hoffe meine Frage sprengt nicht all zu sehr den Rahmen des Forums, aber hätte eine
Frage zur C Sortierung. Ich habe versucht eine kleine Namenssortierung zu programmieren,
aber das Programm gibt mir die Namen nur irgendwie aus, und nicht der Reihe nach
sortiert. Was genau heißt es eigentlich, wenn ein String "größer" oder "kleiner" als
der andere ist? In meinem C Buch steht das zB bei strcmp dabei: < 0 bedeutet str1 ist
kleiner als str2. Ist hier die Länge gemeint oder wie? Selbst wenn, werden die Namen im
Programm trotzdme nur irgendwie sortiert.

strcmp() gibt < 0 zurück, wenn der erste String alphabetisch kleiner als der zweite ist,
0 wenn sie gleich sind und > 0 wenn der zweite String alphabetisch kleiner als der zweite
ist. Alphabetische Sortierung ist dier ein Begriff? Der Stellenwert eines Zeichens ergibt
sich dabei aus seinem ASCII-Wert.

#include <iostream.h>

C++

#include <conio.h>

Borland C

#include <string.h>

C

Du mischt C++ und C, tue das nicht nie nicht. C ist nur scheinbar eine Teilmenge von C++.
Entweder, du schreibst C oder du schreibst C++.

#define AZ 5 /*Anzahl der Namen, die eingegeben werden können */
#define LA 15 /*Länge der Namen */

typedef char namen[AZ][LA];

Sowas tut man nicht in C.

void nameneinlesen(namen &einlesestrings)    {

Das ist wieder C++.

cout << "Gib den Namen " << (i + 1) << "ein: ";
           cin >> einlesestrings[i];

C++

cout <<"Sortierte Ausgabe:\n";
[...]
           cout <<ausgabestrings[i] <<"\n";

Und wieder C++

Was möchtest du programmieren? C oder C++?

Grüße,
 CK

[Markus Trusk]

Hallo,

#include <iostream.h>
C++

#include <conio.h>

Borland C

#include <string.h>
C

Ok conio.h ist überflüssig, habe es vergessen hinaus zu geben, aber string.h benötige ich nun mal.

Du mischt C++ und C, tue das nicht nie nicht. C ist nur scheinbar eine Teilmenge von C++.
Entweder, du schreibst C oder du schreibst C++.

#define AZ 5 /*Anzahl der Namen, die eingegeben werden können */
#define LA 15 /*Länge der Namen */

typedef char namen[AZ][LA];

Ja, ich meine eigentlich auch C++ :)

Sowas tut man nicht in C.

void nameneinlesen(namen &einlesestrings)    {

Das ist wieder C++.

cout << "Gib den Namen " << (i + 1) << "ein: ";
           cin >> einlesestrings[i];

C++

cout <<"Sortierte Ausgabe:\n";
[...]
           cout <<ausgabestrings[i] <<"\n";

Und wieder C++

Ja,  C++, aber es gibt es einfach nicht alphabetisch aus. Wenn ich folgende Namen eingebe:

andalucia
safet
markus
thomas
birgit

bekomme ich folgende Ausgabe:

safet
markus
thomas
birgit
andalucia

..meiner Meinung nach irgendwie durchgewürfelt und nicht so wie es sein soll, also alphabetisch, hmmm?

Markus Trusk.

[Christian Kruse]

Hallo Markus,

Ja,  C++, [...]

Dann schreib auch C++ ;-)

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(int argc,char *argv[]) {
  vector<string> str_v;
  string tmp;
  unsigned int i,max;

do {
    cin >> tmp;
    if(tmp != "exit") {
      str_v.push_back(tmp);
    }
  } while(tmp != "exit");

for(max=str_v.size()-1;max>0;--max) {
    for(i=0;i<max;++i) {
       if(str_v[i]>str_v[i+1]) {
         tmp        = str_v[i];
         str_v[i]   = str_v[i+1];
         str_v[i+1] = tmp;
       }
    }
  }

for(i=0;i<str_v.size();i++) {
    cout << str_v[i] << endl;
  }

return 0;
}

Ein kleiner Bubblesort-Algorithmus.

Grüße,
 CK

[Christoph Zurnieden]

Hallo zusammen,

Ja,  C++, [...]

Dann schreib auch C++ ;-)

Ja eben! ;-)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>

#ifdef _WIN32
using namespace std;

pragma warning(disable:4786) // strings werden laaaang ;-)

#endif

using namespace std;

int main (void)
{

// Hier rein kommen alle Strings während der
  // Benutzer sie fleißig eingibt.
  vector<string> v;

// alle eingebeben Strings kommen an's Ende des Vectors v
  copy (istream_iterator<string> (cin),
          istream_iterator<string> (),
          back_inserter (v));

// sortieren. Aber Vorsicht: ist nur ASCII!
  sort (v.begin(), v.end());

// Vector ausgeben, oben anfangen.

//Erstmal 'n Strich ;-)
   cout << "______________________________________________" << endl;
  //Dann die eigentliche Ausgabe
   copy (v.begin(), v.end(),
          ostream_iterator<string> (cout, "\n"));

//Wir sind _ordentliche_ Schlampen! ;-)
  return 0;
}

Bauen (falls der GCC zur Hand, für andere Compiler bitte in die Doku schauen. Die WIN-Anpassung habe ich mir schon erlaubt zu tätigen):

bash $ gcc -W -Wall -pedantic -ansi -o sort sort.cpp -lstdc++

Ausprobieren:

bash $ ./sort
sdf
hjk
ert
wer
ölkj
äsdf
(^D)
_________________________________________
ert
hjk
sdf
wer
äsdf
ölkj

Das ^D in Klammern bedeutet, das in der Bash STRG+D gedrückt werden muß, damit das Dingen das passende Signal bekommt.

Viel Spaß beim Ausbauen wünscht

Christoph Zurnieden

[MudGuard]

Hi,

void sortieren(namen &einlesestrings)    {
            for (i = 0; i < AZ; i++)    {
                  if (strcmp(einlesestrings[i], einlesestrings[i+1]) < 0)    {
                  strcpy(temp, einlesestrings[i+1]);
                  strcpy(einlesestrings[i+1], einlesestrings[i]);
                  strcpy(einlesestrings[i], temp);
                  }
            }

Was auch immer das ist - ein Sortier-Algorithmus ist das nicht - Du läufst lediglich ein einziges Mal über Dein Array.
Wenn das ein Sortier-Algorithmus wäre, wäre dieser linear, also O(n).
Wenn ich mich richtig erinnere, sind die besten bekannten Sortieralgorithmen bei O(n log n), die schlechten in der Gegend von O(n^2).

Deine Schleife sorgt dafür, daß das kleinste Element am Ende des Arrays landet, wenn ich das richtig sehe.

cu,
Andreas

[Tim Tepaße]

Hallo MudGuard,

Wenn ich mich richtig erinnere, sind die besten bekannten Sortieralgorithmen
bei O(n log n),

Jupp

die schlechten in der Gegend von O(n^2).

Wetten, wenn ich mich anstrenge, kriege ich garantiert noch schlechtere
hin? ;-)

Tim

[MudGuard]

Hi,

die schlechten in der Gegend von O(n^2).
Wetten, wenn ich mich anstrenge, kriege ich garantiert noch schlechtere hin? ;-)

;-)

cu,
Andreas