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.



  • @isaanu92

    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.


Log in to reply