Sortierverfahren 'Direktes Vertauschen (Bubble Sort)' und 'Direkte Auswahl (Selection Sort)'
-
Hallo, könnte mir jemand helfen , wie ich diese Aufgabe lösen kann . ?
Beim Sortierverfahren 'Direktes Vertauschen (Bubble Sort)' finden für eine aufsteigende Sortierung eines Containers mit n Elementen innerhalb einer äußeren Schleife mehrere Durchläufe einer inneren Schleife durch den Container statt. In jedem Durchlauf der inneren Schleife werden jeweils benachbarte Paare von Werten verglichen. Falls ein Paar die falsche Reihenfolge hat (der kleinere Wert ist weiter hinten), werden die beiden Werte innerhalb des Containers vertauscht. Falls ein Paar schon die richtige Reihenfolge hat, wird nichts gemacht. Da auf diese Weise ein kleiner Wert in jedem Durchlauf der inneren Schleife nur um eine Position nach vorn wechseln kann, sind im ungünstigsten Fall (n-1) Durchläufe der äußeren Schleife für eine vollständige Sortierung erforderlich. Schreiben Sie ein Funktionstemplate bubbleSort, das einen Container vom Typ T (T ist also beispielsweise array<int,100> oder vector<string>) als Parameter übernimmt und den beschriebenen Algorithmus auf den Container anwendet, um ihn aufsteigend (d.h. genauer gesagt: 'nicht absteigend': der auf einen Wert folgende Wert ist größer als oder gleich wie der Vorgänger) zu sortieren. Das Sortierverfahren 'Direkte Auswahl (Selection Sort)' durchsucht einen unsortierten Container in der inneren von zwei geschachtelten Schleifen zunächst nach dem kleinsten Element. Danach wird das kleinste Element mit dem ersten Element des Containers ausgetauscht. Dieser Prozess wird für die unsortierten Teilcontainer, die mit dem zweiten, dann dem dritten, vierten, usw. Element des Containers beginnen, wiederholt. Jeder derartige Durchlauf durch den Container bewirkt, dass ein weiteres Element an die Stelle kommt, an die es gehört. Sobald der unsortierte Teilcontainer nur noch ein Element enthält, ist der Container sortiert. Im ungünstigsten Fall sind auch hier (n-1) Durchläufe der äußeren Schleife erforderlich. Schreiben Sie ein Funktionstemplate selectionSort, das einen Container vom Typ T als Parameter übernimmt und diesen Algorithmus auf den Container anwendet, um ihn nicht absteigend zu sortieren. Schreiben Sie außerdem ein Funktionstemplate lessEqualSorted, das einen Container vom Typ T als Parameter übernimmt und true zurückgibt, falls der Container aufsteigend (d.h. 'nicht absteigend') sortiert ist, false falls dies nicht der Fall ist. Testen Sie Ihre Sortierfunktionen, indem Sie ein mit zufälligen ganzen Zahlen gefülltes array<int,100> und danach einen mit mindestens fünf Wörtern in zunächst unsortierter Reihenfolge gefüllten vector<string> sortieren und die Sortierergebnisse mit lessEqualSorted überprüfen.
-
Lesen, verstehen, implementieren.
-
könnte mir jemand helfen , wie ich diese Aufgabe lösen kann . ?
Ziemlich sicher ja. Wie weit bist du denn bisher gekommen und womit hast du konkret Probleme?
ps: Wie man Fragen richtig stellt https://tty1.net/smart-questions_de.html
-
@hustbaer das wäre echt gut... ich lerne noch C++ daher bin ich mit dieser Aufgabe leicht am verzweifeln wie sieh auszusehen hat.
Das habe ich bis jetzt geschrieben:```cpp
#include<iostream>
using namespace std;
void swapping(int &a, int &b) { //swap the content of a and b
int temp;
temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void bubbleSort(int *array, int size) {
for(int i = 0; i<size; i++) {
int swaps = 0; //flag to detect any swap is there or not
for(int j = 0; j<size-i-1; j++) {
if(array[j] > array[j+1]) { //when the current item is bigger than next
swapping(array[j], array[j+1]);
swaps = 1; //set swap flag
}
}
if(!swaps)
break; // No swap in this pass, so array is sorted
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; //create an array with given number of elements
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
bubbleSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
}Mein Problem liegt darin das ich nicht weis ob das so richtig ist mit der Aufgabenstellung, in der Vorlesungen haben wir diese Programm durch genommen:```cpp // Sorting a container into ascending order with merge sort. #include <iostream> #include <array> #include <vector> #include <string> #include <cstdlib> #include <ctime> using namespace std; template < typename T > void displayElements(const T& container, size_t low, size_t high); template < typename T > void mergeSort(T& container, size_t low, size_t high); template < typename T > void mergeSortHelper(T& container, size_t low, size_t high, T& combined); template < typename T > void merge(T& container, size_t left, size_t middle1, size_t middle2, size_t right, T& combined); int main() { srand(static_cast<unsigned>(time(nullptr))); const size_t SIZE{ 10 }; // array size array< int, SIZE > a{ 77, 63, 69, 41, 39, 75, 58, 12, 16, 15 }; cout << "Unsorted array:" << endl; displayElements(a, 0, a.size() - 1); // print unsorted array cout << endl; mergeSort(a, 0, a.size() - 1); // sort array cout << "Sorted array:" << endl; displayElements(a, 0, a.size() - 1); // print sorted array vector< string > v{ "Foxtrott", "Alfa", "Papa", "Uniform", "Charly", "Kilo" }; cout << "\n\nUnsorted vector:" << endl; displayElements(v, 0, v.size() - 1); // print unsorted vector cout << endl; mergeSort(v, 0, v.size() - 1); // sort vector cout << "Sorted vector:" << endl; displayElements(v, 0, v.size() - 1); // print sorted vector } // display container elements from index low through index high template < typename T > void displayElements(const T& container, size_t low, size_t high) { for (size_t i{ 0 }; i < low; ++i) { // display spaces for alignment cout << " "; } for (size_t i{ low }; i <= high; ++i) { // display relevant elements cout << " " << container[i]; } cout << endl; } template < typename T > // function that starts a merge sort void mergeSort(T& container, size_t low, size_t high) { T combined{ container }; // not-in-place working container mergeSortHelper(container, low, high, combined); } // recursive function to sort (sub)container template < typename T > void mergeSortHelper(T& container, size_t low, size_t high, T& combined) { if ((high - low) >= 1) { // if not base case (container with size 1) size_t middle1{ (low + high) / 2 }; // calculate middle of container size_t middle2{ middle1 + 1 }; // calculate next element over // output split step cout << "split: "; displayElements(container, low, high); cout << " "; displayElements(container, low, middle1); cout << " "; displayElements(container, middle2, high); cout << endl; // split container in half; sort each half (recursive calls) mergeSortHelper(container, low, middle1, combined); // first half mergeSortHelper(container, middle2, high, combined); // second half // merge two sorted containers after split calls return merge(container, low, middle1, middle2, high, combined); } } // merge two sorted subcontainer into one sorted subcontainer template < typename T > void merge(T& container, size_t left, size_t middle1, size_t middle2, size_t right, T& combined) { size_t leftIndex{ left }; // index into left subcontainer size_t rightIndex{ middle2 }; // index into right subcontainer size_t combinedIndex{ left }; // index into not-in-place working container // output two subcontainers before merging cout << "merge: "; displayElements(container, left, middle1); cout << " "; displayElements(container, middle2, right); // merge container until reaching end of either while (leftIndex <= middle1 && rightIndex <= right) { // place smaller of two current elements into result // and move to next index in container if (container[leftIndex] <= container[rightIndex]) combined[combinedIndex++] = container[leftIndex++]; else combined[combinedIndex++] = container[rightIndex++]; } if (leftIndex == middle2) { // if at end of left container while (rightIndex <= right) // copy in rest of right container combined[combinedIndex++] = container[rightIndex++]; } else { // at end of right container while (leftIndex <= middle1) // copy in rest of left container combined[combinedIndex++] = container[leftIndex++]; } // copy values back into original container for (size_t i{ left }; i <= right; ++i) { container[i] = combined[i]; } // output merged container cout << " "; displayElements(container, left, right); cout << endl; }
Ich weiß wie Bubble und Selection Sort arbeiten aber das in einem Programm zu schreiben dabei habe ich noch Probleme. Könntest du mir vielleicht mit einem Ansatz helfen?
-
Du lernst also in der Vorlesung C++ mit Containern und Funktionstemplates und schreibst dann in der Hausaufgabe C mit cout?
-
@manni66 was meinst du?
-
void bubbleSort(int *array, int size)
fällt dir ein Unterschied auf?
template < typename T > void mergeSort(T& container, size_t low, size_t high);
-
Der Code ist von hier: https://docplayer.org/72947731-Arrays-und-vectors-suchen-und-sortieren-2006-pearson-education-inc-all-rights-reserved.html falls es jemanden interessiert auf welchem Niveau da gearbeitet wird.