Beim Sortieralgorithmus Index merken

[Bayer22 (Gast)]

Guten Tag,
ich habe hier einen Sortieralgorithmus (bubble sort).
Dieser Sortiert die Elemente eines Arrays von klein nach groß.
Gibt es eine Möglichkeit den Algo so zu erweitern, dass man die alte 
Position des Eintrags, also den alten Index merkt?
Es soll folgendes möglich sein:
Index: 0 1 2
Array: 2 1 4

Nach dem sortieren:

Index: 1 0 2
Array: 1 2 4

Hier der Algorithmus:

#include <stdio.h>
#include <stdlib.h>

#define Elementenzahl 3

void bubble(unsigned char *array, unsigned char elemente) {
   unsigned char i,temp,AlterIndex[3];
   while(elemente--){
      for(i = 1; i <= elemente; i++){
         if(array[i-1] > array[i]) {
            temp=array[i];
            array[i]=array[i-1];
            array[i-1]=temp;

         }
     }
}
}

int main(void)
{
unsigned char TheArray[3]={2,1,4};

bubble(TheArray, Elementenzahl);

printf("Elemente: %d und %d und %d",TheArray[0],TheArray[1],TheArray[2]);

return 0;

}

Wäre für einen Tipp sehr dankbar!

[Phantomix (Gast)]

Das ist ganz einfach. Du legst dir ein zweites Array an. Vor dem 
Sortieren trägst du da die Zahlen von 0...n ein, sodass gilt

TheArray[n] = TheArray[IndexArray[n]]

logisch.

Beim Sortieren verfährst du wie üblich, nur dass du sowohl den Eintrag 
im TheArray als auch im IndexArray äquivalent tauschen musst. also 
nehmen wir an du tauschst TheArray[i1] mit TheArray[i2], dann musst du 
auch IndexArray[i1] mit IndexArray[i2] tauschen.

[Bayer22 (Gast)]

Hier der Code.. meintest du so? :)

#include <stdio.h>
#include <stdlib.h>

#define Elementenzahl 3

void bubble(unsigned char *array, unsigned char *AlterIndex, unsigned char elemente) {
   unsigned char i,temp,tempindex;
   while(elemente--){
      for(i = 1; i <= elemente; i++){
         if(array[i-1] > array[i]) {
                       
            temp=array[i];
            tempindex=AlterIndex[i];
            array[i]=array[i-1];
            AlterIndex[i]=AlterIndex[i-1];
            array[i-1]=temp;
            AlterIndex[i-1]=tempindex;

         }
     }
     
     
}

}

int main(void)
{
unsigned char TheArray[3]={2,1,4};
unsigned char AktuellerIndex[3]={0,1,2}; //== Alter Index!

bubble(TheArray, AktuellerIndex, Elementenzahl);

printf("Aktueller index: %d und %d und %d\n",AktuellerIndex[0],AktuellerIndex[1],AktuellerIndex[2]);
printf("Elemente: %d und %d und %d",TheArray[0],TheArray[1],TheArray[2]);

return 0;

}

Ist ja eigentlich einfach.. aber wenn man auf dem Schlauch steht, steht 
man da halt drauf. :)


Vielen Dank!

[Karl H. (kbuchegg)]

Bayer22 schrieb:
> Hier der Code.. meintest du so? :)

Im Grunde ja.
Bei größeren Datensätzen geht man sogar soweit, dass man nur den Index 
umsortiert und die Daten selber in Ruhe lässt.

D.h. das Datenarray bleibt so wie es war und wenn man die Daten in 
sortierter Form haben möchte, dann greift man so


   array[ AlterIndex[i] ]

darauf zu.

[Sam .. (sam1994)]

Ich würde Klassen sortieren, welche von IComperable abgeleitet sind. In 
der Klasse wird der alte Index gespeichert.

[Bayer22 (Gast)]

Karl Heinz Buchegger schrieb:
> D.h. das Datenarray bleibt so wie es war

Also ich habe jetzt keine großen Datensätze aber heißt das, dass man das 
Datenarray nicht per Pointer übergibt?
Die Information über das Datenarray muss ja im Sortieralgorithmus 
vorhanden sein.

Samuel K. schrieb:
> Ich würde Klassen sortieren, welche von IComperable abgeleitet sind. In
> der Klasse wird der alte Index gespeichert.

Und jetzt bitte nochmals für einen Normalsterblichen! :)
Dachte das IComperable nur bei C# verwendet wird?


Grüße

[Karl H. (kbuchegg)]

Bayer22 schrieb:
> Karl Heinz Buchegger schrieb:
>> D.h. das Datenarray bleibt so wie es war
>
> Also ich habe jetzt keine großen Datensätze aber heißt das, dass man das
> Datenarray nicht per Pointer übergibt?
> Die Information über das Datenarray muss ja im Sortieralgorithmus
> vorhanden sein.

Natürlich muss das Sortierverfahren die Daten kennen, wie soll sie die 
denn sonst sortieren?
Aber sie verändert nun mal nicht die Daten selber, sondern nur den Index


Das ist die Ausgansgsituation.
Die Daten

    +---+---+---+---+---+---+
    | h | a | l | p | e | u |
    +---+---+---+---+---+---+

dazu macht man sich einen Index

    +---+---+---+---+---+---+
    | h | a | l | p | e | u |
    +---+---+---+---+---+---+

    +---+---+---+---+---+---+
    | 0 | 1 | 2 | 3 | 4 | 5 |
    +---+---+---+---+---+---+


und sortiert lediglich den Index so um

    +---+---+---+---+---+---+
    | h | a | l | p | e | u |
    +---+---+---+---+---+---+

    +---+---+---+---+---+---+
    | 1 | 4 | 0 | 2 | 3 | 5 |
    +---+---+---+---+---+---+


dass die Daten beim Zugriff über   daten[ index[ i ] ]
eine sortierter Reihenfolge herauskommen.

Mit einer Schleife

   for( i = 0; i < 6; ++i )
     sprintf( "%c ", daten[index[i]] );

würde man erhalten
    a e h l p u

index[0] ist 1, mit dieser 1 in die Daten: daten[1] ergibt nun mal a
index[1] ist 4, mit dieser 4 in die Daten: daten[4] ergibt nun mal e
etc


ergo:
Das Datenarray bleibt wie es war. Da wird nichts verändert. Aber man hat 
über den Index einen 2-ten Zugriffsweg und wenn man den benutzt, dann 
bekommt man die Daten sortiert geliefert.

Der Umbau des Sortierverfahrens ist trivial. Alle Zugriffe (für die 
Vergleiche) werden bereits über das Index Array geführt und vertauscht 
werden nur die Indices

   while(elemente--){

      for(i = 1; i <= elemente; i++){

         if(array[index[i-1]] > array[index[i]]) {
                       
            tempindex=AlterIndex[i];
            AlterIndex[i]=AlterIndex[i-1];
            AlterIndex[i-1]=tempindex;
         }
     }

[Bayer22 (Gast)]

Ich weis ja was du meinst. Ich hätte den Code so modifiziert:

#include <stdio.h>
#include <stdlib.h>

#define Elementenzahl 3


void bubble(unsigned char *array, unsigned char *AlterIndex, unsigned char elemente) {
   unsigned char i,tempindex;
   while(elemente--){
      for(i = 1; i <= elemente; i++){
         if(array[AlterIndex[i-1]] > array[AlterIndex[i]]) {
                   

            tempindex=AlterIndex[i];
            AlterIndex[i]=AlterIndex[i-1];
            AlterIndex[i-1]=tempindex;
    

         }
     }
     
     
}

}

int main(void)
{
unsigned char TheArray[3]={2,1,4};
unsigned char AktuellerIndex[3]={0,1,2}; //== Alter Index!

bubble(TheArray, AktuellerIndex, Elementenzahl);

printf("Aktueller index: %d und %d und %d\n",AktuellerIndex[0],AktuellerIndex[1],AktuellerIndex[2]);
printf("Elemente: %d und %d und %d",TheArray[0],TheArray[1],TheArray[2]);
// Zugriff auf sortiertes Element, z.b. TheArray[AktuellerIndex[0]] würde // 1 ergeben.
return 0;

}

Denke so müsste es passen.


Vielen Dank!

[Sam .. (sam1994)]

Bayer22 schrieb:
> Und jetzt bitte nochmals für einen Normalsterblichen! :)
> Dachte das IComperable nur bei C# verwendet wird?

sry, ich war aus irgendeinem Grund beim Schreiben bei c#.
In c++ geht das sicher auch. Meine Idee war es jedem Element seinen 
Index (oder ID) mitzuspeichern. Das ganze in einer Klasse kapseln und 
den Index beim vergleichen außen vor lassen.

Wie man Klassen in c++ vergleicht weiß ich aber wirklich nicht. Brauchte 
ich auch bisher noch nicht, da ich in c++ nur Spiele schreibe.