Selection Sort (Array)
-
Hi Leute, wir haben unlängst mit C++ angefangen und nun gibt es folgende Aufgabe:
Gegeben ist ein Array a der Größe size mit paarweise verschiedenen
Elementen aus einem total geordneten Universum.
Wir sollen nun ein Programm schreiben, welches zuerst das größte Element aus a findet
und es mit dem letzten Element aus a vertauscht. Das restliche Array soll dann
rekursiv sortiert werden. Die Funktion selection sort hat folgende Signatur:void selectsort(int a[], int size)
Vorab erstmal meine Frage:
Da steht ja das Array a hat die Größe size mit paarweise
verschiedenen Elementen. Heißt das, dass der Benutzer aufgefordert wird eine Zahl
einzugeben, welche dann der Anzahl der Elementenpaare im Array entspricht?
Also wenn der Nutzer z.B. 10 eingibt, dann hat das Array 20 Elemente?
Nur muss ich doch vorab angeben die größe des Arrays definieren oder?Lassen wir mal kurz das Finden des größten Elementes aus dem Array ausser Acht.
Dann würde ich so anfangen:int main (void) { int a[16]; // hier muss ich doch schon angeben wie groß das Array sein soll oder? cout << "Gib die Anzahl der paarweise verschiedenen Elemente des Arrays an: "; cin >> size; }
Ich danke euch schon mal für eure Unterstützung!
-
Paarweise verschieden heißt nur, daß keine 2 Elemente gleich sind.
Woher die Größe des Arrays kommt, ist der Funktion völlig egal (d.h. ob als Konstante oder aber zur Laufzeit).
Am besten also ersteinmal folgendes benutzen:const int size = 10; int a[size]; // array füllen selectsort(a, size);
Die Größe muß explizit bei der Funktion angegeben werden, weil int a[] nichts anderes als int a* entspricht, d.h. nur die Anfangsadresse des Arrays übergeben wird.
-
Zu deiner Frage, ob erstmal der Benutzer etwas eingeben soll: Du schreibst doch selbst "Gegeben ist ein Array a der Größe size mit paarweise verschiedenen
Elementen aus einem total geordneten Universum.". Dieses Array ist also gegeben. Eine Benutzereingabe ist zur Lösung dieser Aufgabe nicht nötig.Umgekehrt: ich würde die empfehlen, ein paar verschiedene Beispielarrays zu machen, mit denen du dann deine zu schreibende Funktion testen kannst.
Also z.B. so:
void selectsort(int a[], int size) { ... } int main(/* in C++ wird im Gegensatz zu C KEIN void benötigt */) { int testarray[] = { 8, 42, 23, 17 }; // Länge kann automatisch ermittelt werden selectsort(testarray, sizeof(testarray) / sizeof(testarray[0])); std::cout << "Array sortiert:\n"; for (const auto &val : testarray) std::cout << val << " "; std::cout << "\n"; }
Es sei noch angemerkt, dass die Paramterübergabe mit einem Pointer und einer Länge sehr nach C aussieht - in modernem C++ würde man das anders lösen. Ist für dein Problem aber jetzt eigentlich erstmal egal.
-
Hey Leute! Danke euch, das Programm läuft jedoch musste ich in meine Signatur noch was dazutun, damit die Funktion rekursiv ist. Sie sieht jetzt so aus:
void selectsort ( int a[], int size, int index = 0 )
Iterativ hat es ohne index = 0 geklappt.
-
Wozu benötigst du diesen zusätzlichen Paramter? Das Problem lässt sich auch ohne diesen Paramter rekursiv lösen - ich sehe nicht einmal, warum dieser Parameter gut sein sollte!
-
Man muss ein Array nicht immer komplett weitergeben:
#include <iostream> void print( int arr[], int len ) { for( int i = 0; i < len; ++i ) { std::cout << arr[i] << " "; } std::cout << "\n"; } int main() { const int arr_len = 4; int arr[arr_len] = { 1, 2, 3, 4 }; print( arr, arr_len); print( arr, arr_len - 1 ); print( arr + 2, arr_len - 2 ); }
-
Also das ist jetzt der gesamte Code:
#include <iostream> using namespace std; //gibt den kleinsten Index zurück int min_index ( int a[], int i, int j ) { if (i == j) return i; //finde das kleinste der verbliebenden Elemente int k = min_index (a, i + 1, j); //gibt aus dem aktuellen und der verbliebenden Elemente das kleinste zurück return ( a[i] < a[k] )? i : k; } void selectsort ( int a[], int size, int index = 0 ) { // Ausgabe, wenn Anfang und size gleich sind if ( index == size ) return; // Aufruf der min_index Funktion, um den kleinsten Index zu erhalten int k = min_index ( a, index, size - 1 ); // Tausche, wenn der kleinste Index ungleich dem Index ist if ( k != index ) swap ( a[k], a[index] ); // rekursiver Aufruf von selectsort selectsort ( a, size, index + 1 ); } // Ausgabe des Arrays void ausgabe_a ( int a[], int size ) { for ( int i = 0; i < size; ++i ) { cout << a[i] << " "; } cout << endl; } int main () { int a[] = { 4, 1, 5, 3, 2 }; int size = sizeof ( a ) / sizeof ( a[0] ); cout << "Array unsortiert: "; ausgabe_a(a, 5); cout << endl; selectsort (a, size); cout << "Array sortiert: "; ausgabe_a(a, 5); cout << endl; }
wahrscheinlich bissel umständlich ^ ^
-
// rekursiver Aufruf von selectsort selectsort ( a, size, index + 1 );
manni66 schrieb:
Man muss ein Array nicht immer komplett weitergeben
welches zuerst das größte Element aus a findet
Wie hängt das mit min_index zusammen?
-
In der Aufgabenstellung hieß es, dass das größte Element gefunden und nach hinten geschoben werden sollte. Du suchst das kleinste
Daher:
void selectsort(int a[], int size) { // Wir sind fertig, wenn das zu sortierende Array nur 1 Element lang ist if (size <= 1) return; // sonst: gröten Index finden int largestElementIdx = max_index(a, size); // ...und mit letztem Element tauschen if (largestElementIdx != size - 1) swap(a[largestElementIdx], a[size - 1]); // jetzt den Rest des Arrays sortieren selectsort(a, size - 1); }
-
manni66 schrieb:
Man muss ein Array nicht immer komplett weitergeben
Okay, ich habs jetzt noch mal anders geschrieben
manni66 schrieb:
welches zuerst das größte Element aus a findet
manni66 schrieb:
Wie hängt das mit min_index zusammen?
Ja stimmt, es soll ja das größte genommen werden. Jetzt so:
void selectsort ( int a[], int size ) { int max_index = 0, temp = 0, index = 0; //finde das größte Element for ( index = max_index; index < size; ++index ) { if ( a[index] > a[max_index] ) { max_index = index; } } // hier wird getauscht temp = a[size-1]; a[size-1] = a[max_index]; a[max_index] = temp; if ( size > 1 ) { // rekursiver Aufruf selectsort ( a, --size ) ; } }
jetzt funktioniert's auch ohne den Zusatz von davor in der Signatur