diff options
Diffstat (limited to 'Bachelor/Prog1/Prakt5/prg1p5_2/main.cpp')
| -rw-r--r-- | Bachelor/Prog1/Prakt5/prg1p5_2/main.cpp | 178 |
1 files changed, 178 insertions, 0 deletions
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 |