Neues Beispiel: Insertion Sort
authorAndreas Bilke <andreas@bilke.org>
Tue, 25 Jul 2017 11:30:52 +0000 (13:30 +0200)
committerAndreas Bilke <andreas@bilke.org>
Tue, 25 Jul 2017 11:30:52 +0000 (13:30 +0200)
Insertionsort/cpp/Makefile [new file with mode: 0644]
Insertionsort/cpp/insertionsort.cpp [new file with mode: 0644]

diff --git a/Insertionsort/cpp/Makefile b/Insertionsort/cpp/Makefile
new file mode 100644 (file)
index 0000000..234aae3
--- /dev/null
@@ -0,0 +1,5 @@
+all:
+       g++ -Wall -o insertionsort insertionsort.cpp
+
+clean:
+       -rm insertionsort
diff --git a/Insertionsort/cpp/insertionsort.cpp b/Insertionsort/cpp/insertionsort.cpp
new file mode 100644 (file)
index 0000000..b6bb2c0
--- /dev/null
@@ -0,0 +1,74 @@
+/*!
+ * \file insertionsort.cpp
+ * \brief Generiert Zufallszahlen und sortiert sie anschließend mittels Insertion Sort
+ *
+ * \author Andreas Bilke, M. Sc.
+ * \copyright GNU Public License
+ */
+
+#include <cstdlib>
+#include <ctime>
+
+#include <iostream>
+#include <string>
+#include <vector>
+
+void insertionsort(std::vector<int>& zahlen);
+
+/*!
+ * \brief Einstiegspunkt für das Programm "insertionsort".
+ *
+ * \param argc Die Anzahl der Kommandozeilenparameter
+ * \param argv Die Kommandozeilenparameter
+ * \return Den Erfolgsstatus des Programms
+ */
+int main(int argc, char** argv) {
+    int laengeArray;
+
+    std::string zeilenpuffer;
+
+    std::cout << "Wie viele Zahlen sollen generiert werden? ";
+    std::getline(std::cin, zeilenpuffer);
+    laengeArray = std::stoi(zeilenpuffer);
+
+    std::vector<int> zahlen(laengeArray);
+
+    std::srand(std::time(0));
+    for (int i = 0; i < laengeArray; i++) {
+        zahlen[i] = std::rand() % 1000;
+    }
+
+    std::cout << "Unsortierte Zahlen:" << std::endl;
+    for (int i = 0; i < laengeArray; i++) {
+        std::cout << zahlen[i] << " ";
+    }
+    std::cout << std::endl;
+
+    std::cout << "Sortierte Zahlen:" << std::endl;
+    insertionsort(zahlen);
+    for (int i = 0; i < laengeArray; i++) {
+        std::cout << zahlen[i] << " ";
+    }
+    std::cout << std::endl;
+
+    return EXIT_SUCCESS;
+}
+
+/**
+ * \brief Implementierung von Insertion Sort
+ *
+ * Sortiert die Zahlen direkt im übergebenen Array.
+ *
+ * \param zahlen Der zu sortierende Vektor/Array
+ */
+void insertionsort(std::vector<int>& zahlen) {
+    for (size_t i = 1; i < zahlen.size(); i++) {
+        int wert = zahlen[i];
+        size_t j = i;
+        while (j > 0 && zahlen[j - 1] > wert) {
+            zahlen[j] = zahlen[j - 1];
+            j--;
+        }
+        zahlen[j] = wert;
+    }
+}