Time-Complexity-Tests/BubbleSort.cpp at master · canyoucsharp/Time-Complexity-Tests · 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
#include "Header.h"


double Sorting::bubbleTime(int arr[], int n)
{
	clock_t start, end;

	int * hold = arr;

	start = clock();
	int i, j, temp;
		for (i = 0; i < n - 1; i++)

			// Last i elements are already in place
			for (j = 0; j < n - i - 1; j++)
				if (hold[j] > hold[j + 1])
				{
					temp = hold[j];
					hold[j] = hold[j + 1];
					hold[j + 1] = temp;

				}
		end = clock();
		double msecs = ((double)(end - start)) * 1000 / CLOCKS_PER_SEC;

		return msecs;

	}

int Sorting::bubbleSteps(int arr[], int n)
{
	int * hold = arr;
	int i, j, temp, numofsteps = 0;

	numofsteps++; //initialize
	for (i = 0; i < n - 1; i++)
	{
		numofsteps+=2;//i++, i<n-1
		// Last i elements are already in place
		for (j = 0; j < n - i - 1; j++)
		{
			numofsteps+=2;//i<n-j, i++
			if (hold[j] > hold[j + 1])
			{
				temp = hold[j];
				hold[j] = hold[j + 1];
				hold[j + 1] = temp;
				numofsteps+= 4; //hold[i]>hold[i+1], tmp = hold[i], hold[i]=hold[i+1], hold[i+1]=tmp

			}
			numofsteps++;//hold[i] < hold[i+1]
		}
		numofsteps++; //i>n-j
	}
	numofsteps++; //swapped == false
	return numofsteps;
}


double Sorting::improved_bubbleTime(int arr[], int n)
{
	clock_t start, end;
	bool swapped = true;
	int j = 0, tmp;
	int * hold = arr;

	start = clock();
	while (swapped) {
		swapped = false;
		j++;
		for (int i = 0; i < n - j; i++) {
			if (hold[i] > hold[i + 1]) {
				tmp = hold[i];
				hold[i] = hold[i + 1];
				hold[i + 1] = tmp;
				swapped = true;
			}
		}
	}
	end = clock();
	double msecs = ((double)(end - start)) * 1000 / CLOCKS_PER_SEC;
	return msecs;
}

int Sorting::improved_bubbleSteps(int arr[], int n)
{
	bool swapped = true;
	int j = 0, tmp, numofsteps=0;
	int * hold = arr;
	numofsteps++;//initialize

	while (swapped)
	{
		swapped = false;
		j++;
		numofsteps += 3; //(swapped), j++, swapped=false
		for (int i = 0; i < n - j; i++)
		{
			numofsteps += 2;//i<n-j, i++
			if (hold[i] > hold[i + 1])
			{
				tmp = hold[i];
				hold[i] = hold[i + 1];
				hold[i + 1] = tmp;
				swapped = true;
				numofsteps += 5; //hold[i]>hold[i+1], tmp = hold[i], hold[i]=hold[i+1], hold[i+1]=tmp, swapped=true
			}
			numofsteps++;//hold[i] < hold[i+1]
		}
		numofsteps++; //i>n-j
	}
	numofsteps++; //swapped == false
	return numofsteps;
}