#include <stdio.h>#include <stdlib.h>#include <time.h>#include <conio.h>int *A;int length;int i,j, choice,userchoice;int k;void lengthDefine ();/*defines the length of the array to be sorted*/void initialize();/* defines the entries of the array to be sorted*/void sortDefine();/*defines the sorting algorithm to be applied and applies it*/void swap(int *, int *); /*exchange algorithm*/void SS(int P[],int); /*the Selection Sort algorithm.*/int part (int P[], int, int, int);/*partition algorithm*/void QSL (int P[], int, int);/*Quick Sort, last entry defines partition*/void QSR (int P[], int, int, int);/*Quick Sort, random entry defines partition*/void mergeSort(int *array,int left, int right);void merge(int *array, int left, int middle, int right);void sort(int arr[], int beg, int end,int p);void main(){ printf("Press 1 to begin a new test.\n"); printf("Press 2 to exit.\n"); scanf("%d",&choice); if (choice==2) exit(1); else if(choice==1) { lengthDefine ();//orizo to mikos tou pinaka initialize();//orizo ta stoixeia tou pinaka sortDefine(); for (i=0;i<length;i++) { printf("%d\n", A[i]); } main(); } else { printf("***Please choose from the numbers above!***\n"); main(); }}void lengthDefine (){ printf("Choose the length of the array to be sorted. \n"); scanf("%d",&length); A = (int*)calloc(length,sizeof(int)); if (A==NULL) { printf("***Not enough memory!***\n"); exit(1); }}void initialize(){ printf("Choose the method of initialisation: \n"); printf("Press 1 for random initialisation. \n"); printf("Press 2 for an 'almost sorted' initialisation\n"); printf("Press 3 for manual initialisation\n"); scanf("%d",&choice); switch(choice) { case 1: { for (i=0; i<length ; i++) A[i] = (int)rand(); for (k=0;k<length;k++) printf("%d ",A[k]); printf("\n"); } break; case 2: { int max; int a; A[0]=10; max=A[0]; for (i=0;i<length-1;i++) { if ((float)rand()/RAND_MAX<=0.9) { A[i+1]=max+1; max=A[i+1]; } else { int a; a=(10*rand()/RAND_MAX); A[i+1]=max-a; } } } break; case 3: { for (i=0;i<length;i++) { printf("Please enter an integer number\n"); scanf("%d",&A[i]); } } break; default: { printf("***Please choose from the numbers above!***\n"); initialize (); } }}void sortDefine(){ printf("Choose the sorting algorithm you wish to apply: \n"); printf("Press 1 for Selection Sort. \n"); printf("Press 2 for Quick Sort (last entry defines particion).\n"); printf("Press 3 for Quick Sort (random entry defines particion).\n"); printf("Press 4 for Merge Sort.\n"); printf("Press 5 to go back to the main menu.\n"); scanf("%d",&choice); switch(choice) { case 1: SS (A,length); break; case 2: { QSL(A , 0, length-1); } break; case 3: { printf("Give the pivot between 0 and %d\n", length); do{ scanf("%d", &userchoice); if((userchoice>=0) && (userchoice<=length)){ printf("wrong data\n"); } }while( (userchoice<=0) && (userchoice>=length)); int p= userchoice; sort(A , 0, length-1, p); } break; case 4: { mergeSort(A,0, length); } break; case 5: { exit(1); } break; }}void SS(int P[],int l){ int pos_min; for (i=0;i<l;i++) { pos_min=i; for (j=i;j<l;j++) { if (P[j]<P[pos_min]) pos_min=j; } swap (&P[i],&P[pos_min]); }}void swap (int *a,int *b){ int temp; temp=*a; *a=*b; *b=temp;}int part(int P[], int min_p , int max_p, int p){ int i = min_p-1; int j = max_p; int v = P[p]; while (1) { while (P[++i]<=v); while (P[--j]>=v); if (j==min_p) break; if (i>=j) break; else swap (&P[j],&P[i]); } if (p>i) swap (&P[i],&P[p]); if (p<i) swap (&P[j],&P[p]); return i;}void QSL(int P[], int min_p, int max_p){ if (max_p <= min_p) return; int n; n = part(P,min_p,max_p,max_p); QSL(P,min_p,n-1); QSL(P,n+1,max_p);}void QSR(int P[], int min_p, int max_p, int p){ int p1; int p2; if (max_p <= min_p)//sort check return; printf("Give the pivot between 0 and %d\n", length); //here there is a kind of bug, but the implementation was easier with this way do{ scanf("%d", &userchoice); }while( (userchoice>=0) && (userchoice<=length)); p1=userchoice; int n; /*n = part(P,min_p,max_p,p); p1=p-min_p; p2=max_p-p+1; */ QSR(P,min_p,max_p,p1); printf("Give the pivot between 0 and %d\n", length); //here there is a kind of bug, but the implementation was easier with this way do{ scanf("%d", &userchoice); }while( (userchoice>=0) && (userchoice<=length)); p2=userchoice; QSR(P,n+1,max_p,p2); /*int p1; int p2; if (max_p <= min_p) return; int n; n = part(P,min_p,max_p,p); p1 = ((n-1+min_p)*rand()/RAND_MAX)+min_p; p2 = ((max_p-n-1)*rand()/RAND_MAX)+n+1; QSR(P,min_p,n-1,p1); QSR(P,n+1,max_p,p2); */}//mergesort numbers arrayvoid mergeSort(int *array,int left, int right){ int middle; if (left!=right){ middle=(right+left)/2; mergeSort(array,left,middle); //mergesort sort left half array mergeSort(array,middle+1,right); //mergesort sort right half array merge(array,left,middle,right); //merge arrays }}//merge the first half array from left to middle index, with the second half array from middle+1 to right indexvoid merge(int *array, int left, int middle, int right) { int ileft=left; int iright=middle+1; int itemp=left; int *temp=(int *)malloc((right+2)*sizeof(int)); while (ileft<=middle && iright<=right) { if (array[ileft] <= array[iright]) { temp[itemp] = array[ileft]; itemp++; ileft++; } else { temp[itemp] = array[iright]; itemp++; iright++; } } while (ileft<=middle) { temp[itemp]=array[ileft]; itemp++; ileft++; } while (iright<=right) { temp[itemp]=array[iright]; itemp++; iright++; } for (itemp=left;itemp<=right;itemp++){ array[itemp] = temp[itemp]; }}void sort(int arr[], int beg, int end,int p) { int piv = p/100*end; if (end > beg + 1) { int l = beg + 1, r = end; while (l < r) { if (arr[l] <= piv) l++; else swap(&arr[l], &arr[--r]); } swap(&arr[--l], &arr[beg]); sort(arr, beg, l,piv); sort(arr, r, end,piv); }}//void swap(int *a, int *b) { int t=*a; *a=*b; *b=t; }