diff options
| author | Sven Eisenhauer <sven@sven-eisenhauer.net> | 2023-11-10 15:11:48 +0100 |
|---|---|---|
| committer | Sven Eisenhauer <sven@sven-eisenhauer.net> | 2023-11-10 15:11:48 +0100 |
| commit | 33613a85afc4b1481367fbe92a17ee59c240250b (patch) | |
| tree | 670b842326116b376b505ec2263878912fca97e2 /Bachelor/Prog1/Prakt5/prg1p5_2 | |
| download | Studium-33613a85afc4b1481367fbe92a17ee59c240250b.tar.gz Studium-33613a85afc4b1481367fbe92a17ee59c240250b.tar.bz2 | |
Diffstat (limited to 'Bachelor/Prog1/Prakt5/prg1p5_2')
| -rw-r--r-- | Bachelor/Prog1/Prakt5/prg1p5_2/main.cpp | 178 | ||||
| -rw-r--r-- | Bachelor/Prog1/Prakt5/prg1p5_2/prg1p5_2.dsp | 100 | ||||
| -rw-r--r-- | Bachelor/Prog1/Prakt5/prg1p5_2/prg1p5_2.dsw | 29 |
3 files changed, 307 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 diff --git a/Bachelor/Prog1/Prakt5/prg1p5_2/prg1p5_2.dsp b/Bachelor/Prog1/Prakt5/prg1p5_2/prg1p5_2.dsp new file mode 100644 index 0000000..8d19b08 --- /dev/null +++ b/Bachelor/Prog1/Prakt5/prg1p5_2/prg1p5_2.dsp @@ -0,0 +1,100 @@ +# Microsoft Developer Studio Project File - Name="prg1p5_2" - Package Owner=<4>
+# Microsoft Developer Studio Generated Build File, Format Version 6.00
+# ** NICHT BEARBEITEN **
+
+# TARGTYPE "Win32 (x86) Console Application" 0x0103
+
+CFG=prg1p5_2 - Win32 Debug
+!MESSAGE Dies ist kein gültiges Makefile. Zum Erstellen dieses Projekts mit NMAKE
+!MESSAGE verwenden Sie den Befehl "Makefile exportieren" und führen Sie den Befehl
+!MESSAGE
+!MESSAGE NMAKE /f "prg1p5_2.mak".
+!MESSAGE
+!MESSAGE Sie können beim Ausführen von NMAKE eine Konfiguration angeben
+!MESSAGE durch Definieren des Makros CFG in der Befehlszeile. Zum Beispiel:
+!MESSAGE
+!MESSAGE NMAKE /f "prg1p5_2.mak" CFG="prg1p5_2 - Win32 Debug"
+!MESSAGE
+!MESSAGE Für die Konfiguration stehen zur Auswahl:
+!MESSAGE
+!MESSAGE "prg1p5_2 - Win32 Release" (basierend auf "Win32 (x86) Console Application")
+!MESSAGE "prg1p5_2 - Win32 Debug" (basierend auf "Win32 (x86) Console Application")
+!MESSAGE
+
+# Begin Project
+# PROP AllowPerConfigDependencies 0
+# PROP Scc_ProjName ""
+# PROP Scc_LocalPath ""
+CPP=cl.exe
+RSC=rc.exe
+
+!IF "$(CFG)" == "prg1p5_2 - Win32 Release"
+
+# PROP BASE Use_MFC 0
+# PROP BASE Use_Debug_Libraries 0
+# PROP BASE Output_Dir "Release"
+# PROP BASE Intermediate_Dir "Release"
+# PROP BASE Target_Dir ""
+# PROP Use_MFC 0
+# PROP Use_Debug_Libraries 0
+# PROP Output_Dir "Release"
+# PROP Intermediate_Dir "Release"
+# PROP Target_Dir ""
+# ADD BASE CPP /nologo /W3 /GX /O2 /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_MBCS" /YX /FD /c
+# ADD CPP /nologo /W3 /GX /O2 /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_MBCS" /YX /FD /c
+# ADD BASE RSC /l 0x407 /d "NDEBUG"
+# ADD RSC /l 0x407 /d "NDEBUG"
+BSC32=bscmake.exe
+# ADD BASE BSC32 /nologo
+# ADD BSC32 /nologo
+LINK32=link.exe
+# ADD BASE LINK32 kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib /nologo /subsystem:console /machine:I386
+# ADD LINK32 kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib /nologo /subsystem:console /machine:I386
+
+!ELSEIF "$(CFG)" == "prg1p5_2 - Win32 Debug"
+
+# PROP BASE Use_MFC 0
+# PROP BASE Use_Debug_Libraries 1
+# PROP BASE Output_Dir "Debug"
+# PROP BASE Intermediate_Dir "Debug"
+# PROP BASE Target_Dir ""
+# PROP Use_MFC 0
+# PROP Use_Debug_Libraries 1
+# PROP Output_Dir "Debug"
+# PROP Intermediate_Dir "Debug"
+# PROP Target_Dir ""
+# ADD BASE CPP /nologo /W3 /Gm /GX /ZI /Od /D "WIN32" /D "_DEBUG" /D "_CONSOLE" /D "_MBCS" /YX /FD /GZ /c
+# ADD CPP /nologo /W3 /Gm /GX /ZI /Od /D "WIN32" /D "_DEBUG" /D "_CONSOLE" /D "_MBCS" /YX /FD /GZ /c
+# ADD BASE RSC /l 0x407 /d "_DEBUG"
+# ADD RSC /l 0x407 /d "_DEBUG"
+BSC32=bscmake.exe
+# ADD BASE BSC32 /nologo
+# ADD BSC32 /nologo
+LINK32=link.exe
+# ADD BASE LINK32 kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib /nologo /subsystem:console /debug /machine:I386 /pdbtype:sept
+# ADD LINK32 kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib /nologo /subsystem:console /debug /machine:I386 /pdbtype:sept
+
+!ENDIF
+
+# Begin Target
+
+# Name "prg1p5_2 - Win32 Release"
+# Name "prg1p5_2 - Win32 Debug"
+# Begin Group "Quellcodedateien"
+
+# PROP Default_Filter "cpp;c;cxx;rc;def;r;odl;idl;hpj;bat"
+# Begin Source File
+
+SOURCE=.\main.cpp
+# End Source File
+# End Group
+# Begin Group "Header-Dateien"
+
+# PROP Default_Filter "h;hpp;hxx;hm;inl"
+# End Group
+# Begin Group "Ressourcendateien"
+
+# PROP Default_Filter "ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe"
+# End Group
+# End Target
+# End Project
diff --git a/Bachelor/Prog1/Prakt5/prg1p5_2/prg1p5_2.dsw b/Bachelor/Prog1/Prakt5/prg1p5_2/prg1p5_2.dsw new file mode 100644 index 0000000..b0380fc --- /dev/null +++ b/Bachelor/Prog1/Prakt5/prg1p5_2/prg1p5_2.dsw @@ -0,0 +1,29 @@ +Microsoft Developer Studio Workspace File, Format Version 6.00
+# WARNUNG: DIESE ARBEITSBEREICHSDATEI DARF NICHT BEARBEITET ODER GELÖSCHT WERDEN!
+
+###############################################################################
+
+Project: "prg1p5_2"=.\prg1p5_2.dsp - Package Owner=<4>
+
+Package=<5>
+{{{
+}}}
+
+Package=<4>
+{{{
+}}}
+
+###############################################################################
+
+Global:
+
+Package=<5>
+{{{
+}}}
+
+Package=<3>
+{{{
+}}}
+
+###############################################################################
+
|