sortier- und suchalgorithmen

[mirscho]

hi leutz!

kann mir bitte einer von euch mal mir zwei Sortier- Suchalgorithmen
erklären ( also Bubble- und Quicksort z.B. ) ( find nix anständiges )

auch ein ( guter ) Link auf eine site wäre nich schlecht!
was sonst noch interessant wäre, ist, ob jemand von euch eine site kennt wo alle möglich struktogram dinge mal aufgezeichnet sind...also wie z.B. das struktogramm für eine for schleife aussieht.

thx4help un schön tag noch

 

[Daniel Toplak]

Also bezüglich Stuktogramme gab es schon mal einen Thread hier:

http://www.tutorials.de/forum/showthread.php?threadid=14120&highlight=struktogramme

Da hab ich zig Links über Struktogramme usw. gepostet.

Zu Sortieralogrithmen:
Die Verwendung hängt meist von den Daten ab, die sortiert werden müssen. Kennen tu ich vom Namen her folgende:
- Bubble Sort
- Shell Sort
- Heap Sort
- Insert Sort

Die Algorithmen kann ich dir net aufzeigen, außer zum Bubble Sort der wohl einfachste aber zugleich langsamste.

Das Prinzip des Bubble Sorts basiert auf 2 Schleifen, die ineinander geschachtelt sind, die "äußere" hat als Abbruchkriterium meist einen Schalter, (nennen wir ihn mal BOOL getauscht), das heißt die "äußere" Schleife läuft solange, bis etwas getauscht wird. Die Innere läuft die Anzahl der Objekte -1 druch, die man sortieren will. Diese Anzahl der Objekte wir pro Durchlauf der "äußeren" Schleife um 1 verringert, da der BubbleSort garantiert, das nach dem 1. Druchlauf "der Größte" Wert am Ende steht. Beim 2. Durchlauf steht dann der "2 größte" Wert an vorletzter Stelle. (daher auch der Name Bubble Sort, weil die Werte wie Luftblasen "aufsteigen". Inherhalb der "inneren Schliefe" werden die Werte dann miteinander verglichen. Das heißt: ist der aktuelle Wert größer als der nächste, dann wird der aktuelle Wert in eine temporär-Variable gespeichert und die Werte werden vertauscht, dann wird der temporär-Wert an den nächsten Wert zugewiesen.

Leider kann ich das nich verständlicher mit Worten ausdrücken darum werde ich noch ein ganz einfaches Code-Beispiel dazu schreiben. Das Beispiel ist reines C für die Konsole, also ganz einfach gehalten, um das Prinzip zu verstehen:

#include <stdio.h>

void main()
{
	int arr[] = {5,234,43,4356,4,56,23,456,34,6547}; // Test-Array mit 10 int-Werten

	printf("Die Werte unsortiert: ");
	for (int i=0; i<10; i++)			
	{
		printf("%d, ", arr[i]);			// Ausgabe des Array
	}
	
	printf("\n\n");						// Zwei Leerzeilen
	bool getauscht = true;				// Schalter für die äußere Schleife
	int anzahl = 10;					// Anzahl der Werte, die Sortiert werden
	int temp;							// temporär-Variable
	while(getauscht)					// äußere Schleife
	{
		getauscht = false;				// am Anfang der äußeren Schleife mal auf falsch setzen
		
		for (i=0; i<anzahl-1; i++)		// innere Schleife
		{
			if(arr[i]>arr[i+1])			// Abfrage, ob der aktuelle Wert größer als der nächste ist
			{
				temp = arr[i];			// dann wird der aktuelle in die temp-Variable geschrieben
				arr[i] = arr[i+1];		// die Werte werden getauscht
				arr[i+1] = temp;		// der Wert der temp-Variable wir an den nächsten zugewießen
				getauscht = true;		// der Schalter wir auf true gesetzt;
			}
		} // Ende innere Schleife
		anzahl --;						// veringern, der inneren Schleifendurchläufe, weil bei jedem äußeren
										// Durchlauf, der größte Wert am Ende Steht;
	} //  Ende äußere Schleife

	printf("Die Werte sind jetzt sortiert: ");
	for (i=0; i<10; i++)			
	{
		printf("%d, ", arr[i]);			// Ausgabe des Array
	}
	printf("\n\n");						// Zwei Leerzeilen
}

Gruss Homer

 

[mirscho]

jo...das haut so hin thx!!

das mit dem sortier dings hab ich nur noch nich so ganz verstanden...naja...werds schon hinkriegen moin...

schön abend denn...

 

[Radhad]

weiß jemand, wie ich einen sortieralgorithmus schreibe für ein 2 dimensionales feld int messung[3][25] ?

ich hab da mal was probiert, aber das programm stürzt dabei ab...

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

int messung[3][25]; //2-dimensionales Feld

void Sortieralgorithmus(void)
{
	int k, l, m, n, temp;

	for(k=0;k<=3;k++);
	{
		for(l=0;l<=25;l++)
		{
			for(m=0;m<=3;m++)
			{
				for(n=0;n<=25;n++)
				{
					if(messung[k][l]>messung[m][n]) //Abfrage was kleiner ist
					{
						temp=messung[k][l];			//Tauschvorgang
						messung[k][l]=messung[m][n];
						messung[m][n]=temp;
					}
				}
			}
		}
	}
}

void main()
{
	char nochmal;
	int i, j;

	do
	{
		for(i=0;i<=3;i++)
		{
			for(j=0;j<=25;j++)
			{
				do
				{
					printf("Bitte geben Sie nur Werte zwischen 0 und 99 ein!\n\n");
					printf("Bitte geben Sie den %d. Wert der %d. Messreihe ein: ",i+1,j+1);
					scanf("%d",&messung[i][j]);
					fflush(stdin);
					system("cls");
				}
				while(messung[i][j]<0 || messung[i][j]>99); //nur weiter im richtigen Wertebereich!
			}
		}

		for(i=0;i<=3;i++)
		{
			for(j=0;j<=25;j++)
			{
				printf("%2d",messung[i][j]);
			}
			printf("\n");
		}

		Sortieralgorithmus();

		for(i=0;i<=3;i++)
		{
			for(j=0;j<=25;j++)
			{
				printf("%2d",messung[i][j]);
			}
			printf("\n");
		}

		do
		{
			printf("Wollen Sie das Programm erneut starten?\n\n");
			printf("  [J] JA\n  [N] NEIN\n\n");
			printf("Auswahl: ");
			scanf("%c",&nochmal);
			fflush(stdin);
			system("cls");
		}
		while(nochmal!='j' && nochmal!='J' && nochmal!='n' && nochmal!='N'); //nur weiter bei j oder n!
	}
	while(nochmal=='j' || nochmal=='J');
}

 

[Frankdfe]

Hallo

Ich sehe 2 Fehler in deinem Programm:

1.

int messung[3][25]; //2-dimensionales Feld
...
for(i=0;i<=3;i++)

int messung[3][25] hat 3*25 Felder
messung[0,1,2]
messung[3] gibt es nicht also darf die For-Schleife nicht bis 3 zählen (und die anderen nicht bis 25).

2.

for(k=0;k<=3;k++);

Der Semikolon am Zeilenende ist wohl ein Tippfehler

Gruß Frank

 

[Radhad]

jo, das fiel mir dann auch auf *g* den fehler habe ich schon behoben, trotzdem wird bei mir nichts sortiert ^^ sondern nur durcheinander geworfen

int messwerte[3][25], messwerteneu[3][25];

void sortieralgorithmus(void)
{
	int k, l, m, n, temp;

	for(k=0;k<=2;k++)
	{
		for(l=0;l<=4;l++)
		{
			messwerteneu[k][l]=messwerte[k][l];
		}
	}

	m=0;

	for(k=0;k<=2;k++)
	{
		for(l=0;l<=4;l++)
		{
			n=l+1;
			if(l==4 && k==0)
			{
				n=0;
				m=1;
			}
			if(l==4 && k==1)
			{
				n=0;
				m=2;
			}
			for(m;m<=2;m++)
			{
				for(n;n<=4;n++)
				{
					if(messwerteneu[m][n]<messwerteneu[k][l])
					{
						temp=messwerteneu[k][l];
						messwerteneu[k][l]=messwerteneu[m][n];
						messwerteneu[m][n]=temp;
					}
				}
				n=0;
			}
		}
	}
}