// Ue6Aufgabe2.cpp : Defines the entry point for the console application.///**@author Wolfgang Miller 612437@author Nassim Mouafi 626387**/#include <iostream>#include <stdlib.h>#include <vector>#include <fstream>int *randomArray(int size);void selectionSort(int *unsortiert, int size);int getPivot(int *array, int l, int r);void exchange(int *array, int p, int q);int binarySearch(int *array, int size, int value, int *compares);void insert(int value);int find(int value, int *compares);/**Main - Funktion**//**int *randomArray(int size)erstellt ein Array mit Zufallszahlen@param size**/int *randomArray(int size){ int *reihung = new int [size]; int zufall; for (int i=0; i < size; i++){ zufall = (int)((float)rand() / (float)RAND_MAX * 16383.0f); reihung[i] = zufall; } return reihung;}/**void sort(int *unsortiert, int groesse)Selection SortSortiert die Werte des Arrays das durch den Zeiger *unsortiert referenziert wird.@param int *unsortiert@param int groesse**/void selectionSort(int *unsortiert, int groesse){ bool eintritt; while(groesse > 0){ eintritt = true; int vergleich; for (int i = 0; i < groesse; i++) { if(eintritt) { vergleich = i; eintritt = false; } if (unsortiert[vergleich] < unsortiert[i]) { vergleich = i; } } exchange(unsortiert, vergleich, groesse-1); groesse--; eintritt = true; } return;}/**void exchange(int *intArray, int p, int q )Tauscht Indexwerte p und q auf dem int Array auf das der Zeiger *intArray zeigt.@param int *intArray @param int p@param int q**/void exchange(int *intArray, int p, int q ){ int zwischenspeicher; zwischenspeicher = intArray[p]; intArray[p] = intArray[q]; intArray[q] = zwischenspeicher; return;}/**int binarySearch(int *array, int size, int value, int *compares)Sucht einen Wert auf dem übergebenen Array.@param int *array@param int size@param int value@param int *compares**/int binarySearch(int *array, int size, int value, int *compares){ int mitte = size/2; (*compares)++; if (array[mitte] == value) { return 1; } if (size == 1) { return 0; } (*compares)++; if (array[mitte] > value) { size = mitte; return binarySearch(array, size, value, compares); } else { return binarySearch(&array[mitte+1], size - mitte, value, compares); }};/**Klasse mit Nodes für die Skiplist@param value @param h @param head **/class SkiplistNode{public: vector<SkiplistNode*> next; int value; SkiplistNode(int value, int h, vector<SkiplistNode*> &head) { this->value = value; for(int i=0; i<h; i++) { next.push_back(head[i]); head[i] = this; } }};class Skiplist{public: vector<SkiplistNode*> head; /** Ein neues Element wird in die Skipliste eingefügt @param value @param h_in **/ void insert(int value, int h_in) { int h = 1; if (h_in == 0) { while (rand() < (RAND_MAX/2)) h++; } else { while ((rand()<(RAND_MAX/2)) && (h < h_in)) h++; } while (head.size() < h) head.push_back(NULL); new SkiplistNode(value,h,head); } /** Sucht in der Liste nach dem Element mit dem Wert value @param value @param *compares **/ int find(int value, int *compares) { *compares=0; vector<SkiplistNode *> *p_akt = &head; int max_size = head.size()-1; while (max_size >= 0) { if ((*p_akt)[max_size] == NULL) max_size--; else { *compares = *compares + 1; if ((*p_akt)[max_size]->value < value) p_akt = &((*p_akt)[max_size]->next); else { *compares = *compares + 1; if ((*p_akt)[max_size]->value == value) return 1; max_size--; } } } return 0; } ~Skiplist() { SkiplistNode *tmp1 = head[0]; while (tmp1 != NULL) { SkiplistNode *tmp2 = tmp1; tmp1 = tmp1->next[0]; delete tmp2; } }};int main(int argc, char* argv[]){ int nMin = -1; int nMax = -1; int mAnzZufallsz = -1; if(argc != 4 ||((nMin && nMax && mAnzZufallsz) > 1 || atoi(argv[1]) > atoi(argv[2]))) { std::cout << "Bitte Zahlen >0 übergeben!" << std::endl; return 0; } else{ nMin = atoi(argv[1]); nMax = atoi(argv[2]); mAnzZufallsz = atoi(argv[3]); } for (int i = nMin; i <= nMax;i++) { int size = i; int compares = 0; int *reihung = randomArray(size); /* for (int i = 0; i< size; i++) { std::cout << "Unsortiert: " <<reihung[i]<<std::endl; }*/ selectionSort(reihung, size); /* for (int i = 0; i< size; i++) { std::cout << "Sortiert: " <<reihung[i]<<std::endl; }*/ for (int i = 0; i < mAnzZufallsz; i++) { int value = (int)((float)rand() / (float)RAND_MAX * 16383.0f); int peter = binarySearch(reihung, size, value, &compares); std::cout << std::endl; std::cout << "Gesucht: " << value << std::endl; std::cout << "n: " <<size << std::endl; std::cout << "Gefunden: " << peter << " Vergleiche: " << compares << std::endl; compares = 0; } std::cout << std::endl; } std::cout << std::endl; //system("Pause"); return 0;}