From 33613a85afc4b1481367fbe92a17ee59c240250b Mon Sep 17 00:00:00 2001 From: Sven Eisenhauer Date: Fri, 10 Nov 2023 15:11:48 +0100 Subject: add new repo --- Bachelor/Prog1/Prakt5/prg1p5_2/main.cpp | 178 ++++++++++++++++++++++++++++ Bachelor/Prog1/Prakt5/prg1p5_2/prg1p5_2.dsp | 100 ++++++++++++++++ Bachelor/Prog1/Prakt5/prg1p5_2/prg1p5_2.dsw | 29 +++++ 3 files changed, 307 insertions(+) create mode 100644 Bachelor/Prog1/Prakt5/prg1p5_2/main.cpp create mode 100644 Bachelor/Prog1/Prakt5/prg1p5_2/prg1p5_2.dsp create mode 100644 Bachelor/Prog1/Prakt5/prg1p5_2/prg1p5_2.dsw (limited to 'Bachelor/Prog1/Prakt5/prg1p5_2') 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 + +using std::cin; +using std::cout; +using std::endl; + +#include + +using std::setprecision; +using std::setw; + +// contains function prototypes for functions srand and rand +#include + +#include + +// 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 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> +{{{ +}}} + +############################################################################### + -- cgit v1.2.3