Algorithms_code/quicksort.c at main · Bindusrinaik04/Algorithms_code · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
//1.generate random number and store them in the file.
//2.use the file and apply the quick sort on them.
//3.apply randomized quick sort on the same
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void quicksort(int[],int,int);
void quicksortrandom(int[],int,int);
int partition(int[],int,int);
int partitionrandom	(int[],int,int);
void swap(int*,int*);

//swap function
void swap(int* a,int* b){
int temp=*a;
*a=*b;
*b=temp;
}

//dividing the array
void quicksort(int arr[],int start,int end){
if(start<end){
int p = partition(arr,start,end);
 //printf("%d\n",p); //printing pivot point
quicksort(arr,start,p-1);
quicksort(arr,p+1,end);
}

}

//main code for quick sort
/*------------Usual implementation of quick sort--------------------------*/
int partition(int arr[],int low,int high){

 int pivot=arr[high];
 int i,j;
 i=low-1;
 j=low;
 for(;j<=high-1;j++){
 if(arr[j]<pivot){
 i++;
 swap(&arr[i],&arr[j]);
 }
 }
 i++;
 swap(&arr[i],&arr[high]);

 return i;

}

/*-----------------------randomized quick sort----------------------------------*/
void quicksortrandom(int arr[],int start,int end){
if(start<end){
int p = partitionrandom(arr,start,end);
 //printf("%d\n",p); //printing pivot point
quicksortrandom(arr,start,p-1);
quicksortrandom(arr,p+1,end);
}

}

int partitionrandom(int arr[],int low,int high){

 int pivot=low+rand()%(high-low+1); //high-low+1 [select random index as pivot
 printf("\n pivot element : %d\n",pivot);
 swap(&arr[pivot],&arr[high]);  //swap pivot indexed with last element in the array
 pivot = arr[high];

 int i,j;
 i=low-1;
 j=low;
 for(;j<=high-1;j++){
 if(arr[j]<pivot){
 i++;
 swap(&arr[i],&arr[j]);
 }
 }
 i++;
 swap(&arr[i],&arr[high]);

 return i;

}

int main(){

 /*int n=6,i;
 int arr[]={10,7,8,9,1,5};
 quicksort(arr,0,n-1);
for(i=0;i<n;i++) printf("%d\t",arr[i]);
*/
srand(time(NULL));

/*---------------generating random numbers and saving it to file------------------------*/
FILE *input = fopen("randomnumbers.txt","w");
if(!input){ printf("error in opening file"); return 1;}

int n=10; //total number of random numbers generated
for(int i=0;i<n;i++){
int num = rand()%100;
fprintf(input,"%d\n",num);
}

fclose(input);

/*-----------------taking input from file-------------------------*/

FILE *fp=fopen("randomnumbers.txt","r");
if(!fp){ printf("error in opening file"); return 1;}

int arr[n]; //size declared above
for(int i=0;i<n;i++){
 	if(fscanf(fp,"%d",&arr[i])!=1) {
		 printf("error while readin values to array");
 		 fclose(fp);
 	         return 1;
                }
              }
fclose(fp);

/*----------------------quick sort algorithm----------------------------------*/
 quicksort(arr,0,n-1);
 for(int i=0;i<n;i++) printf("%d\t",arr[i]);
 printf("\n");
 quicksortrandom(arr,0,n-1);
 for(int i=0;i<n;i++) printf("%d\t",arr[i]);
return 0;
}