Zahlen sortieren

EEK

http://www.tu-harburg.de/~salb0470/Uni%20Stuff/Info2/vcppk/bubble_sort.html

xnn

suchalgorithmen stehen auch in tafelwerk und informatik aber nur wie sie funzen und was die idee dahinter ist, schreiben musst du sie noch selber M;(

mfg XeNoN

David_pb

Hi!

Willst du selbst ein Sortieralgo schreiben? Gibt ja schon diverse Lösungen:

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>

void DumpVec( const std::vector< int > &v )
{
	std::vector< int >::const_iterator i = v.begin();

	for ( ; i != v.end(); ++i )
		std::cout << *i << " ";

	std::cout << std::endl;
}

int main( int argc, char **argv )
{
	std::vector< int > v;

	srand( static_cast< unsigned >( time( NULL ) ) );

	for ( int i = 0; i < 10; i++ )
		v.push_back( rand() );

	std::cout << "Vor der Sortierung\n";
	DumpVec( v );

	std::sort( v.begin(), v.end() );

	std::cout << "Nach der Sortierung\n";
	DumpVec( v );

	std::cin.get();

	return 0;
}

grüße

waldemator

hi ihr

das problem, diese fertiglösungen sind alle etwas zu komplex, es muss ein ganz einfaches und kleines und unkompliziertes programm sein!

ich kann mit den vector etc. nichts anfangen, deswegen war auch mein anfang des quelcodes "einfach"

gruß

David_pb

Hi!

Was is daran jetzt so schwer? Informiert dich halt, dann lernst du gleich was dabei.

void sort( int *v, int size )
{
	for ( int i = size-1; i >= 0; i-- )
	{
		for ( int j = 0; j <= i-1; j++ )
		{
			if ( v[ j ] > v[ j+1 ] )
			{
				short tmp = v[ j ];
				v[ j ] = v[ j+1 ];
				v[ j+1 ] = tmp;
			}
		}
	}
}

grüße

waldemator

hallo,also ich bin jetzt mal nur 3 zahlen ausgegangen, also dass 3 zahlen sortiert werden müssten...

bin zu diesem ergebnis gekommen:

#include <iostream.h>
#include <stdio.h>

void BubbleSort(int Array)

{
        int iZahl=0;
        int imax;
        int i;
        int temp;
        for (imax=0;imax<2;imax++)
        {
                for (i=0;i<2;i++)
                {
                        if (i<2)
                        {
                                 if (Array[i] > Array [i+1])
                                {
                                        temp=Array[i];
                                        Array[i]=Array[i+1];
                                        Array[i+1]=temp;
                                 }       
                         }
                 }
         }
}

jetzt bleibt er die ganze zeit bei der zweiten IF abfrage hängen und kommt nicht weiter, ich habe das gefühl ihm aber allerdings der abschluss noch, nur ich komme nicht dahinter...

könnt ihr mir weiter helfen...???

gruß

ceplusplus

Grüße!

while(!sorted) 
    { 
        sorted = true; 

        for(unsigned short i = 0; i < (max-1); i++) 
        { 

            if(unsorted[i] > unsorted[i+1]) 
            { 
                sorted = false; 
                temp = unsorted[i+1]; 
                unsorted[i+1] = unsorted[i]; 
                unsorted[i] = temp; 
            } 
        } 
    }

Bin noch Anfänger und habe es sogar selbst geschrieben.
Einfacher geht es kaum, einfache Erklärung:

Der Vektor wird so oft durchgelaufen, bis nicht mehr vertauscht werden kann.
Wenn in einem Durchgang vertauscht wird, wird der if-Block ausgelöst und sorted = false. Daher, wenn in einem Durchgang nichts mehr getauscht werden kann, bleibt sorted = true und die Zahlen sind fertig sortiert.

Es wird das jeweilige Element mit dem Nachbarelement verglichen und eventuell vertauscht.

Wirklich ganz simpel.

//EDIT:
Hier noch laufender Code, siehe auch mein Thema etwas weiter unten.
(Wegen Variablen temp und so...):

int main() 
{ 
    const max = 5; 
    unsigned short temp; 
    unsigned short unsorted[max]; 
    bool sorted = false; 

    cout << "Geben Sie " << max << " Zahlen ein: " << endl; 
    for(unsigned short c = 0; c < max; c++) 
        cin >> unsorted[c]; 
    cout << "Die Zahlen werden nun aufsteigend sortiert..." << endl << endl; 

    while(!sorted) 
    { 
        sorted = true; 

        //Wenn i das letzte Element ist, wäre i+1 undefiniert?! 
        for(unsigned short i = 0; i < (max-1); i++) 
        { 

            if(unsorted[i] > unsorted[i+1]) 
            { 
                sorted = false; 
                temp = unsorted[i+1]; 
                unsorted[i+1] = unsorted[i]; 
                unsorted[i] = temp; 
            } 
        } 
    } 

    cout << "Ergebnis: " << endl; 
    for(unsigned short x = 0; x < max; x++) 
        cout << unsorted[x] << endl; 
    cout << endl << "Fertig." << endl; 

    return 0; 
}

waldemator

ja gut dass du es kannst, ich kann es nicht, ich muss leider...

programmierung ist das einzige wo ich mich noch richtig schwer tue...

so, jetzt zu deinem queltext, ich muss das programm(quelcode) auf jeden fall mit bubblesort machen

außerdem wollte ich wissen was an meinem code nichts timmt, denn da bin ich mir sicher, dass da nur irgendein "hacken" fehlt...

was genau, das fällt mir aber nicht ein

weiß das jemand sonst?

ceplusplus

Schau dir mal die beiden Codes an:

Dein Code:

oid BubbleSort(int Array)

{
        int iZahl=0;
        int imax;
        int i;
        int temp;
        for (imax=0;imax<2;imax++)
        {
                for (i=0;i<2;i++)
                {
                        if (i<2)
                        {
                                 if (Array[i] > Array [i+1])
                                {
                                        temp=Array[i];
                                        Array[i]=Array[i+1];
                                        Array[i+1]=temp;
                                 }       
                         }
                 }
         }
}

Mein Code:

while(!sorted) 
    { 
        sorted = true; 

        for(unsigned short i = 0; i < (max-1); i++) 
        { 

            if(unsorted[i] > unsorted[i+1]) 
            { 
                sorted = false; 
                temp = unsorted[i+1]; 
                unsorted[i+1] = unsorted[i]; 
                unsorted[i] = temp; 
            } 
        } 
    }

1. Statt "for" nimmst du "while" ganz außen.
2. Unser Code unterscheidet sich nicht wesentlich, nur mit den Schleifen hast du noch Probleme denk ich.
3. Einmal "if" zuviel.

So, jetzt vergleiche unsere Codes, meiner ist die "ausgebesserte" Variante von deinem, und es ist der Bubble-Sort.

//EDIT:
Wichtig ist doch, dass du die äußerste Schleife verlassen musst, wenn in einem Durchlauf der Ausdruck "x[i] > x[i+1]" false hat. Dieser ist false, wenn eben nichts mehr vertauscht wurde, also das letzte Element schon das größte ist.

gaaanz einfach mithilfe der stl:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
 vector<int> zahlen; // da kommen die zahlen rein
 srand(time(NULL)); // zufallsgenerator initialisieren
 for(int i = 0; i < 10; ++i)
  zahlen.push_back(rand()%10); // 10 zufallszahlen zwischen 0 und 9 generieren
 sort(zahlen.begin(), zahlen.end());
 for(int i = 0; i < zahlen.size(); ++i)
  cout << zahlen[i] << endl; // zahlen ausgeben
}

waldemator

ich habe ein passendes struktugramm und laut diesem ist for 2 mal drin...

ich MUSS das so mit bubblesort machen, ist so vorgegeben!

wie kann man meinen code abändern dass es läuft? probiert mal bei euch den aus..

gruß

ceplusplus

Wie oft noch???

Wenn du unbedingt 2x for verwenden willst, dann änder doch meinen Code ab:

while(!sorted) 
    { 
        sorted = true; 

        for(unsigned short i = 0; i < (max-1); i++) 
        { 

            if(unsorted[i] > unsorted[i+1]) 
            { 
                sorted = false; 
                temp = unsorted[i+1]; 
                unsorted[i+1] = unsorted[i]; 
                unsorted[i] = temp; 
            } 
        } 
    }

Bei deinem Code ist außerdem ein "if" zuviel, also schaut es dann sowieso so aus wie bei mir.
Wenn du es nicht schaffst meinen Code abzuändern, dann sag bescheid...

ceplusplus

Weißt du was, bevor du fragst...

const unsigned short max = 5; 
unsigned short temp; 
unsigned short unsorted[max]; 

//unsorted einlesen

for(unsigned short sorted = 0; sorted <= 0;)
{ 
    sorted = 1;
    for(unsigned short i = 0; i < (max-1); i++) 
    { 

        if(unsorted[i] > unsorted[i+1]) 
        { 
            sorted = 0; 
            temp = unsorted[i+1]; 
            unsorted[i+1] = unsorted[i]; 
            unsorted[i] = temp; 
        } 
    } 
} 

//unsorted ausgeben

waldemator

@ ceplusplus

den code läuft nicht (borland c++ 6)

ceplusplus

Und was "läuft nicht"?

ceplusplus

int main() 
{ 
    const max = 5; 
    unsigned short temp; 
    unsigned short unsorted[max]; 

    cout << "Geben Sie " << max << " Zahlen ein: " << endl; 
    for(unsigned short c = 0; c < max; c++) 
        cin >> unsorted[c]; 
    cout << "Die Zahlen werden nun aufsteigend sortiert..." << endl << endl; 

    for(unsigned short sorted = 0; sorted <= 0;)  
    { 
        sorted = 1; 

        for(unsigned short i = 0; i < (max-1); i++) 
        { 
            if(unsorted[i] > unsorted[i+1]) 
            { 
                sorted = 0; 
                temp = unsorted[i+1]; 
                unsorted[i+1] = unsorted[i]; 
                unsorted[i] = temp; 
            } 
        } 
    } 

    cout << "Ergebnis: " << endl; 
    for(unsigned short x = 0; x < max; x++) 
        cout << unsorted[x] << endl; 
    cout << endl << "Fertig." << endl; 

    return 0; 
}

Pellaeon

Der sort aus der STL geht auch ohne vector mit nem stinknormalen Array, wenn du Container nicht magst.
Alternativ gibts auch qsort aus der mitgelieferten C-Bibliothek, machen beide dasselbe: Quicksort