2.3 Pointer und Referenzen

Im folgenden sollen sie an einem kleinen Beispiel einmal den Einsatz von Referenzen und Pointern einüben und dazu die Anwendung von call by value (Übergabe des Wertes als Kopie an eine Funktion) einmal ansehen.

Im untenstehenden Code wird eine swap-Funktion definiert.

Als Hilfe: C++ Referenz.

Unterschiede zwischen Pointern & Referenzen

	Pointer	Referenzen
Initialisierung	int* ip = &i;	int& ir = i;
Zugriff lesend	*ip	ir
Zugriff schreibend	*ip = 5;	ir = 5;
Kann ins „Nichts“ zeigen	Ja	Nein
Kann neu zugewiesen werden	Ja	Nein

Aufgabe: swap Funktion

ToDo:

• Was tut die zuerst angegebene Funktion?

• Führen sie zwei swap-Funktionen ein, die jeweils die Werte der Variablen tauschen.

  • einmal mit Hilfe von Referenzen

  • einmal mit Hilfe von Pointern.

void swap_1(int x, int y)
{
  int h = x;
  x = y; y = h;
}

Click to show

void swap_ref(int& x, int& y) {
    int temp = x;
    x = y;
    y = temp;
}

Click to show

// Funktion, die zwei Werte durch Verwendung von Zeigern vertauscht
void swap_ptr(int* x, int* y) {
  int temp = *x; // Speichern des Werts von x über den Zeiger
  *x = *y; // Zuweisen des Werts von y an x über den Zeiger
  *y = temp; // Zuweisen des gespeicherten Werts von x an y über den Zeiger
}

#include <iostream>

int main () {
    int a = 42;
    int b = 7;
    swap_1( a, b );
    std::cout << "Swap 1   = a: " << a << " , b: " << b << std::endl;
    // Die folgenden Funktionen muessen noch implementiert werden.
    //a = 42; b = 7;
    //swap_ref( a, b );
    //std::cout << "Swap Ref = a: " << a << " , b: " << b << std::endl;
    //a = 42; b = 7;
    //swap_ptr( &a, &b );
    //std::cout << "Swap Ptr = a: " << a << " , b: " << b << std::endl;
}

main()

Aufgabe: Bubblesort

Im folgenden soll die swap-Funktion (Referenzen nutzend, siehe Anmerkung unten) von oben angewandt werden zur Sortierung eines Arrays von int. Dafür soll ein Bubblesort Algorithmus implementiert werden:

Bubblesort

Bubblesort ist ein einfacher vergleichsbasierter Sortieralgorithmus, der wiederholt durch das Array iteriert, benachbarte Elemente vergleicht und sie vertauscht, wenn sie in der falschen Reihenfolge stehen. Der Algorithmus hat seinen Namen von der Art und Weise, wie kleinere Elemente während jedes Durchlaufs nach oben “aufsteigen”, während größere Elemente nach unten “sinken”.

Swfung8, CC BY-SA 3.0 https://creativecommons.org/licenses/by-sa/3.0, via Wikimedia Commons

Algorithmus:

1. Starte mit dem ersten Element des Arrays.

2. Vergleiche es mit dem nächsten Element.

3. Wenn das aktuelle Element größer ist als das nächste Element, tausche sie.

4. Gehe zum nächsten Element und wiederhole Schritte 2-3, bis das Ende des Arrays erreicht ist.

5. Nach dem ersten Durchlauf wird das größte Element an die letzte Position im Array “hochsteigen”.

6. Wiederhole Schritte 2-5 für den verbleibenden unsortierten Teil des Arrays, bis das gesamte Array sortiert ist.

Schlechteste Fallkomplexität = $O(n^2)$: Der schlechteste Fall tritt auf, wenn das Array in umgekehrter Reihenfolge sortiert ist und jedes Paar benachbarter Elemente in jedem Durchlauf vertauscht werden muss.

Beste Fallkomplexität = $O(n)$ Der beste Fall tritt auf, wenn das Array bereits sortiert ist und keine Vertauschungen während irgendeines Durchlaufs erforderlich sind.

Bubblesort ist für große Arrays aufgrund seiner quadratischen Zeitkomplexität nicht effizient und andere effizientere Sortieralgorithmen wie Quick Sort oder Merge Sort werden in der Praxis für größere Datensätze bevorzugt.

ToDo:

• Implementieren sie bubble sort unter Verwendung der swap Funktion.

• Überlegen sie, wie sie bei einer schon sortierten (oder relativ gut vorsortierten) Liste die Laufzeit verbessern können.

#include <iostream>

void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

Click to show

void bubbleSort(int arr[], int size) {
    bool swapped;
    for (int i = 0; i < size - 1; ++i) {
        swapped = false;
        for (int j = 0; j < size - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                // Werte tauschen, falls notwendig
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        // Wenn in dieser Iteration keine Swaps gemacht wurden, ist das Array bereits sortiert
        // und wir können die Schleife vorzeitig verlassen.
        if (!swapped) {
            break;
        }
    }
}

int main() {
    int arr[] = { 1, 2, 3, 4, 5 }; // bereits sortiertes Array
    int size = sizeof(arr) / sizeof(arr[0]); // Größe des Arrays

    std::cout << "Vor der Sortierung: " << std::endl;
    for (int i = 0; i < size; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    // Array sortieren
    bubbleSort(arr, size);

    std::cout << "Nach der Sortierung: " << std::endl;
    for (int i = 0; i < size; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

main()

Anmerkung: Bevorzugung von Referenzen

Im bereitgestellten Beispiel der Swap-Funktion in der Bubblesort-Implementierung wurden Referenzen anstelle von Pointern verwendet, um die Werte von zwei int’s zu vertauschen.

Der Grund für die Verwendung von Referenzen anstelle von Pointern liegt darin, dass Referenzen in C++ eine bequemere und sicherere Möglichkeit bieten, auf ein Objekt zu verweisen, ohne dass eine explizite Dereferenzierung mit dem *-Operator erforderlich ist. Referenzen sind ähnlich wie Pointer, da sie ermöglichen, auf indirektem Wege auf den Wert eines Objekts zuzugreifen und ihn zu ändern, bieten jedoch einige zusätzliche Vorteile:

1. Vereinfachte Syntax: Referenzen verwenden eine einfachere Syntax im Vergleich zu Pointern. Während Pointer eine explizite Dereferenzierung mit dem *-Operator erfordern, können Referenzen direkt verwendet werden, als ob sie das Originalobjekt wären.

2. Automatische Null-Überprüfung: Anders als Pointer können Referenzen nicht null oder nicht initialisiert sein, was das Dereferenzieren von null oder nicht initialisierten Pointern verhindert, was zu undefiniertem Verhalten führen kann.

3. Automatisches Speichermanagement: Referenzen erfordern keine Speicherzuweisung oder -freigabe, da sie lediglich Aliasnamen für vorhandene Objekte sind. Dies beseitigt die Notwendigkeit von Speicherverwaltungsvorgängen wie new und delete, was dazu beitragen kann, Speicherlecks oder andere speicherbezogene Probleme zu verhindern.

4. Typsicherheit: Referenzen sind typsicher, da sie mit einem Objekt desselben Typs initialisiert werden müssen und nicht erneut auf Objekte eines anderen Typs zugewiesen werden können. Pointer hingegen können auf Objekte unterschiedlicher Typen neu zugewiesen werden, was zu typbezogenen Fehlern führen kann.

Im Allgemeinen wird empfohlen, Referenzen gegenüber Pointern zu verwenden, wenn dies möglich ist, da sie eine bequemere und sicherere Möglichkeit bieten, indirekt auf Objekte in C++-Programmen zu arbeiten. Es kann jedoch Fälle geben, in denen Pointer bevorzugt werden, z. B. beim Umgang mit dynamischer Speicherzuweisung oder beim Übergeben von Funktionspointern. Im gegebenen Bubble-Sort-Beispiel wurden jedoch Referenzen aus Gründen der Einfachheit und Sicherheit verwendet.