From 33613a85afc4b1481367fbe92a17ee59c240250b Mon Sep 17 00:00:00 2001
From: Sven Eisenhauer <sven@sven-eisenhauer.net>
Date: Fri, 10 Nov 2023 15:11:48 +0100
Subject: add new repo

---
 Bachelor/Prog1/Prakt5/prg1p5_2/main.cpp | 178 ++++++++++++++++++++++++++++++++
 1 file changed, 178 insertions(+)
 create mode 100644 Bachelor/Prog1/Prakt5/prg1p5_2/main.cpp

(limited to 'Bachelor/Prog1/Prakt5/prg1p5_2/main.cpp')

diff --git a/Bachelor/Prog1/Prakt5/prg1p5_2/main.cpp b/Bachelor/Prog1/Prakt5/prg1p5_2/main.cpp
new file mode 100644
index 0000000..5d5b74e
--- /dev/null
+++ b/Bachelor/Prog1/Prakt5/prg1p5_2/main.cpp
@@ -0,0 +1,178 @@
+// Programmieren 1, Praktikum 5, Aufgabe 2
+// Sven Eisenhauer
+// 16.12.2004
+//
+// file: main.cpp
+//
+// purpose: QuickSort algorithm
+//
+
+#include <iostream>
+
+using std::cin;
+using std::cout;
+using std::endl;
+
+#include <iomanip>
+
+using std::setprecision;
+using std::setw;
+
+// contains function prototypes for functions srand and rand
+#include <cstdlib>
+
+#include <ctime> 
+
+// constant definitions
+const int arraySize=100;         // number of array elements
+const int maxNum=1000;           // max. Number in Array plus 1
+const int arrayStart=0;          // first array element
+const int arrayEnd=arraySize-1;  // last array element
+
+// function prototypes
+void quickSort(int [],int,int);
+int partition(int [], int,int,int&);
+void swapRight(int [], int &,int &, int &, int &, int &);
+void swapLeft(int [], int&,int &, int&, int &, int &);
+
+int main()
+{
+	int array[arraySize];
+
+	// initialize random number generator
+	srand(time(0));
+
+	// generate array with random content
+	for (int i=0;i<arraySize;i++) {
+		array[i]=rand()%maxNum;
+	}
+
+	// show it unsorted
+	cout << "Unsorted:" << endl;
+	for (i=0;i<arraySize;i++) {
+		cout << setw(4) << array[i];
+	}
+	cout << endl;
+
+	// sort it
+	quickSort(array,arrayStart,arrayEnd);
+
+	// show it sorted
+	cout << "Sorted:" << endl;
+	for (i=0;i<arraySize;i++) {
+		cout << setw(4) << array[i];
+	}
+	cout << endl;
+	// habe fertisch
+	return 0;
+}// end function main
+
+void quickSort(int toSort[], int start, int end)
+{
+	int pos;
+	// partition the array and get pos, where array is divided
+	partition(toSort,start,end,pos);
+	if (pos > start)
+		// now sort lower part
+		quickSort(toSort,start,pos-1);
+	if (pos < end)
+		// and higher part
+		quickSort(toSort,pos+1,end);
+}// end function quicksort
+
+int partition(int array[],int start, int end, int &pos)
+{
+	int loop=0;
+	int foundL,foundR;
+	int newStart=start;
+	int newEnd=end;
+	int nextStart=start;
+    
+	pos=start;
+
+	do {
+		foundR=0;
+		foundL=0;
+		// decide whether to search from left or right
+		// 0: right, 1: left
+		if (0==(loop%2)) {
+			swapRight(array,newEnd,newStart,nextStart,pos,foundR);
+			// set newStart for the next call of a swap fct.
+			newStart=nextStart;
+			/*cout << endl << " right "<< loop << " "<< endl;
+			for (int j=0;j<=end;j++)
+				cout << setw(4) << array[j];		
+			cout << endl;*/
+		}
+		else {
+			swapLeft(array,newEnd,newStart,nextStart,pos,foundL);
+			// set newStart for the next call of a swap fct.
+			newStart=nextStart;
+			/*cout << endl << " left "<< loop << " "<< endl;
+			for (int j=0;j<=end;j++)
+				cout << setw(4) << array[j];		
+			cout << endl;*/
+		}
+		loop++;
+	} while (((1==foundL)||(1==foundR)));
+
+	return 0;
+}// end function partition
+
+void swapRight(int arr[], int &end,int &newStart,int &nextStart, int &pos, int &found)
+{
+	int i,temp;
+	// here we start to walk through array, from RIGHT!!!
+	i=end;
+	// newStart is the beginning of the area to check of the array
+	// when newStart==pos (which is the position of we element, which we order at the moment)
+	// this means: we are done here!
+	while((i>=newStart)&&(i!=pos)) {
+		// if we have found a smaller value, when searching from right
+		if (arr[i]<=arr[pos]) {
+			// swap the values
+			temp=arr[i];
+			arr[i]=arr[pos];
+			arr[pos]=temp;
+			// now set the next Start of search from left to one field right of
+			// the element, we currently searched and swapped
+			nextStart=newStart+1;
+			// in i is the actual position of the element which should be ordered
+			// we should not forget this and tell this the place, from where we were called
+			pos=i;
+			// YES!!! we found a smaller value by searching from right
+			found=1;
+			break;
+		}
+		i--;
+	}
+}// end function swapRight
+
+void swapLeft(int arr[], int &end,int &newStart,int &nextStart, int &pos, int &found)
+{
+	int i,temp;
+	// here we start to walk through array, from LEFT!!!
+	i=newStart;
+	// newStart is the beginning of the area to check of the array
+	// when newStart==pos (which is the position of we element, which we order at the moment)
+	// this means: we are done here!
+	while((i<=end)&&(i!=pos)) {
+		// if we have found a bigger value, when searching from left
+		if (arr[i]>arr[pos]) {
+			// swap the values
+			temp=arr[i];
+			arr[i]=arr[pos];
+			arr[pos]=temp;
+			// now set the next Start of search from right to one field left of
+			// the element, we currently searched and swapped
+			nextStart=newStart-1;
+			// in i is the actual position of the element which should be ordered
+			// we should not forget this and tell this the place, from where we were called
+			pos=i;
+			// YES!!! we found a smaller value by searching from right
+			found=1;
+			break;
+		}
+		i++;
+	}
+}// end function swapLeft
\ No newline at end of file
-- 
cgit v1.2.3