Works/QuickSort Implementation at master · akshayarora2009/Works · 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
// algo_QuickSort.cpp : Defines the entry point for the console application.
// Time Analysis of QuickSort Implementation
// Randomly fill up an array 'n' number of times and sort it, record the time and plot a graph for different 'n'

#include "stdafx.h"
#include<stdio.h>
#include<iostream>
#include<conio.h>
#include<limits.h>
#include<time.h>
#include<fstream>
using namespace std;


int Partition(int master[100001],int beg,int end)
{

	int pivot=master[beg];
	int i=beg+1,j=end;
	do
	{
		while(i<end)
		{

			if(master[i]>pivot)
				break;
			i++;

		}

		while(j>beg)
		{

			if(master[j]<pivot)
				break;
			j--;
		}

		if(i<j)
		{
			int temp=master[i];
			master[i]=master[j];
			master[j]=temp;

		}


	}while(i<j);


	if(i>=j)
	{
		int temp2=master[j];
		master[j]=pivot;
		master[beg]=temp2;

		return j;
	}
}


void QuickSort(int master[100001],int beg,int end)
{

	if(beg<end)
	{
		int flag=Partition(master,beg,end);

		QuickSort(master,beg,flag);
		QuickSort(master,flag+1,end);
	}
}


int _tmain(int argc, _TCHAR* argv[])
{
	int A[100001];
	clock_t start,end;

	ofstream MyFile;
	MyFile.open("QSort_av.txt");


	for(int i=4500;i<100001;i+=4500)
	{

		start=clock();
		for(int e=0;e<100;e++)
		{

		for(int j=0;j<i;j++)
		{
			A[j]=rand()%i;
		}

		A[i]=numeric_limits<int>::max();


		QuickSort(A,0,i);

		}
		end=clock();

		MyFile<<i<<","<<(double)(end-start)/CLK_TCK<<endl;
	}


	return 0;
}