C++ Straight Insert

[SasukeX47]

Habe mich bereits ziemlich oft an dem oben genannten Thema verbissen...
Und komme leider nie zu einem gescheiten Ergebnis (Code).

Gegeben: Ein Array Unordnung[] in welchen zufällige Zahlen eingespeist wurden.
Aufgabe: Das Sortieren der Zahlen in einen 2ten Array Ordnung[], in der aufsteigenden Reihenfolge.
Verfahren: Man fahre durch den Array Ordnung[] und suche die exakte Position wo die aktuelle Zahl des Arrays Unordnung[] hineinpasst. Ist die Position gefunden, soll eine "Lücke" aufgemacht werden und die Zahl von Unordnung[] in diese Lücke eingefügt werden.

Ziel: Einblenden von Unordnung[] am Schluss, sowie das Aufzeigen des sortierten Ordnung[].

#include <iostream>
#include <time.h>
using namespace std;

int main()
{
    int Unordnung[10], Ordnung[10];
    int a,i,b,m,c,Ini,Max;
    srand(time(NULL));
    
    for (i=0;i<10;i++)
    {
        Unordnung[i] = rand()%1500;
        Ordnung[i] = 0;
    } 
    cout <<endl;
    Ordnung[0]=Unordnung[0];
    for (i=1;i<10;i++)
    {
        Ini=i;
        c=0;
        a=1;
        m=1;
        for (b=0;b<i;b++)
        {
            if (Unordnung[i]>Ordnung[b])
            { Max=b;c=1;}
        }
        if (c==0) 
        { 
            while(a>0)   
            {
                         if(Ordnung[0]==0)
                         {a=0;}
                         Ordnung[Ini]=Ordnung[Ini-1];
                         Ini--;
            }
            Ordnung[0]=Unordnung[i];
        }
        if (c==1)
        {
            while(m>0) 
            {
                       if(Ordnung[Max]==0)
                       {m=0;}
                       Ordnung[Ini]=Ordnung[Ini-1]; 
                       Ini--;
            }
            Ordnung[Max]=Unordnung[i];
        } 
    }
    for (i=0;i<10;i++)
    {
        cout << " [" << Unordnung[i] << "] ";
    }      
    cout <<endl;
    for (i=0;i<10;i++)
    {
        cout << " [" << Ordnung[i] << "] ";
    }      
    cin >>i;                           
}

Hoffe ihr könnt mir ein bisschen unter die Arme greifen, da ich erst vor kurzem mit C++ angefangen habe...

 

[DerEineDa]

Ich bin mir nicht ganz sicher, aber deine Beschreibung des Sortieralgorithmus klingt für mich sehr nach dem klassischen Insertionsort, aber normalerweise sortiert man damit direkt das Ursprungsarray. Ich habe das für dich mal so umgewandelt, dass in ein anderes Array sortiert wird.

#include <iostream>
#include <time.h>
using namespace std;

int main()
{
    const unsigned elems = 10;
    int Unordnung[elems], Ordnung[elems];
    srand(time(NULL));
    
    for (unsigned i=0;i<elems;i++)
    {
        Unordnung[i] = rand()%1500;
        Ordnung[i] = 0;
    } 
    cout <<endl;
    
    Ordnung[0] = Unordnung[0];
    
    for(unsigned inserted = 1; inserted < elems; ++inserted) {
        int tmp = Unordnung[inserted];
        unsigned ui = inserted;
        while(ui > 0 && Ordnung[ui - 1] > tmp) {
            Ordnung[ui] = Ordnung[ui-1];
            --ui;
        }
        Ordnung[ui] = tmp;
    }
    
    for (unsigned i=0;i<elems;i++)
    {
        cout << " [" << Unordnung[i] << "] ";
    }      
    cout <<endl;
    for (unsigned i=0;i<elems;i++)
    {
        cout << " [" << Ordnung[i] << "] ";
    }      
    cout << endl << "fertig" << endl;
    cin.get();                           
}

Also was mache ich: Da ein einziges Element in einer Datenstruktur trivialerweise immer sortiert ist, füge ich erstmal das erste Element des Unordnungs-Arrays in das Ordnung-Array ein. (Das hast du bei deinem Programm auch so gemacht).

Die inserted-Variable der for-Schleife benutze ich, um mitzuzählen, wieviele Elemente ich bereits im Ordnungs-Array eingefügt habe. Da ich eines bereits eingefügt habe, initialisiere ich die Variable mit 1. Im Rumpf der Schleife wird nun der eigentliche Insertionsort durchgeführt. Dazu schnappe ich mir das nächste Element des Unordnungs-Arrays und füge es nach den Regeln des Insertionsorts an der richtigen Stelle des Ordnungs-Arrays ein. Dazu werden in der while-Schleife alle Elemente vom Ende des Ordnungs-Arrays solange ein nach hinten geschoben, bis an der richtigen Stelle, wo "tmp" eingefügt werden kann, eine Lücke ist. Das Verfahren ist recht ansehnlich im Wikipedia-Artikel beschrieben.

Ich hoffe, ich konnte dir etwas weiterhelfen.