Selection Sort

ThaRealMatix

Hallo,

wir sollten uns folgendes Selection Sort Programm ansehen

#include <iostream>
using namespace std;

void selectionSort(int *array,int length) 
{
	int i,j,min,minat;
	for(i=0;i<(length-1);i++)
	{
		minat=i;
		min=array[i];

      for(j=i+1;j<(length);j++) //select the min of the rest of array
	  {
		  if(min>array[j])   //ascending order for descending reverse
		  {
			  minat=j;  //the position of the min element 
			  min=array[j];
		  }
	  }
	  int temp=array[i] ;
	  array[i]=array[minat];  //swap 
	  array[minat]=temp;

	}

}

void printElements(int *array,int length) //print array elements
{
	int i=0;
	for(i=0;i<10;i++)
    cout<<array[i]<<endl;
}

void main()
{

	int a[]={9,6,5,23,2,6,2,7,1,8};   // array to sort 
    selectionSort(a,10);                 //call to selection sort  
	printElements(a,10);               // print elements
	system("PAUSE");
}

Leider ist mir nicht völlig klar, was die einzelnen Schritte tun. Könnt ihr mir
mir das vielleicht erklären?

CStoll

Woran hapert es denn? Wenn du die einzelnen Befehle von C++ nicht verstehst, hilft ein Blick in deine Leerbücher sicher weiter. Ansonsten kannst du mal in der Wikipedia oder bei Goggle nach "Selection Sort" suchen.

in Kurzfassung:

die äußerste Schleife der sort-Funktion geht der Reihe nach das gesamte Array durch
die innere Schleife sucht den größten Wert im hinteren Bereich des Arrays
die drei Anweisungen dahinter vertauschen diesen Wert mit dem ersten Element des "hinteren Bereiches"
(und da beim nächsten Schleifendurchlauf dieser Block verkleinert wird, wird der vertauschte Wert in der nächsten Runde nicht mehr verglichen)

ThaRealMatix

hm mir ist ehrlich gesagt wohl genau die äußere nicht ganz klar also

for(i=0;i<(length-1);i++)
	{
		minat=i;
		min=array[i];

desweiteren:

for(j=i+1;j<(length);j++)

Dies wird also nur ausgeführt, wenn j (welches i+1 ist) kleiner als die länge ist. Desweiteren wird er hochgezählt.

Heisst das nun, dass an dieser Stelle der array bzw block verkürzt wird, wie du sagst?

CStoll

1. Der Block initialisiert die aktuelle Position des größten Elements auf den Anfang des untersuchten Arraybereiches.

2. Schau dir mal an, was die einzelnen Anweisungen in der for() bewirken - i wird vom Startwert j+1 bis zum Endwert length hochgezählt.

ThaRealMatix

hm wenn ich das richtig sehe, wurde ja vor diesem hier:

for(j=i+1;j<(length);j++) //sucht das minimum vom Rest des Arrays
	  {
		  if(min>array[j])   //aufsteigende Reihenflge
		  {
			  minat=j;  //Position des minimums 
			  min=array[j];
		  }
	  }
	  int temp=array[i] ;
	  array[i]=array[minat];  //Austausch
	  array[minat]=temp;

schon einmal das minimum herausgesucht. Aber wo genau?

CStoll

In der gesamten Schleife (du gehst nacheinander alle Werte durch und merkst dir ihre Position, wenn sie kleiner sind als das bisherige Minimum - also hast du am Ende das Minimum des gesamten Blocks)

PS: Was genau lernst du eigentlich? Hier häufen sich ja deine Threads mit Grundlagen-Problemen.

ThaRealMatix

Hm ich lerne C++, hinke aber hinterher, stimmt wohl. Da ich aber wenn ich überhaupt ne Chance haben will, das Praktikum abgeben muss, frage ich halt hier nach.

Wenn ich hier falsch bin sags, dann lass ichs