C++

Forum

 
Bubble and Selection Sort - Number of Comparisons and Exchanges

Jaydelay (11)
My program performs a bubble sort and selection sort on the same data. I have 3 different arrays (each one has a duplicate, so a total of 6 arrays). I need to see which sorting algorithm is more efficient (which one requires less comparisons and exchanges). I don't know if I have the comparison and interchange counters in the correct places. Could someone please take a look at my code to confirm? Also, suggestions in where to correctly place the counters would be extremely helpful.

Thank you in advance!

Here my code:
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
 
#include <iostream>
using namespace std;

void bubbleSort(int[], int, int &, int &);
void selectionSort(int[], int, int &, int &);

int main()
{
	const int SIZE = 20;            //Size of arrays
	int comparisons_bubble = 0;     //Comparison counter for bubble sort
	int interchanges_bubble = 0;    //Exchange counter for bubble sort
	int comparisons_selection = 0;  //Comparison counter for selection sort
	int interchanges_selection = 0; //Exchange counter for selection sort

	int case1_a[SIZE] = { 95, 90, 85, 80, 75, 70, 65, 60, 55, 50, 45, 40, 35, 30, 25, 20, 15, 10, 5, 0 };
	int case1_b[SIZE] = { 95, 90, 85, 80, 75, 70, 65, 60, 55, 50, 45, 40, 35, 30, 25, 20, 15, 10, 5, 0 };
	int case2_a[SIZE] = { 0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95 };
	int case2_b[SIZE] = { 0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95 };
	int case3_a[SIZE] = { 40, 70, 20, 15, 5, 65, 80, 85, 0, 95, 25, 35, 30, 60, 45, 10, 50, 55, 90, 75 };
	int case3_b[SIZE] = { 40, 70, 20, 15, 5, 65, 80, 85, 0, 95, 25, 35, 30, 60, 45, 10, 50, 55, 90, 75 };

	bubbleSort(case1_a, SIZE, comparisons_bubble, interchanges_bubble);
	selectionSort(case1_b, SIZE, comparisons_selection, interchanges_selection);

	comparisons_bubble = 0;
	interchanges_bubble = 0;
	comparisons_selection = 0;
	interchanges_selection = 0;

	bubbleSort(case2_a, SIZE, comparisons_bubble, interchanges_bubble);
	selectionSort(case2_b, SIZE, comparisons_selection, interchanges_selection);

	comparisons_bubble = 0;
	interchanges_bubble = 0;
	comparisons_selection = 0;
	interchanges_selection = 0;

	bubbleSort(case3_a, SIZE, comparisons_bubble, interchanges_bubble);
	selectionSort(case3_b, SIZE, comparisons_selection, interchanges_selection);

	return 0;
}

void bubbleSort(int array[], int size, int &comparisons_bubble, int &interchanges_bubble)
{
	bool swap;
	int temp;

	do
	{
		swap = false;

		for (int count = 0; count < (size - 1); count++)
		{
			comparisons_bubble++;
			if (array[count] > array[count + 1])
			{
				interchanges_bubble++;
				temp = array[count];
				array[count] = array[count + 1];
				array[count + 1] = temp;
				swap = true;
			}
		}
	} while (swap);
}

void selectionSort(int array[], int size, int &comparisons_selection, int &interchanges_selection)
{
	int startScan, minIndex, minValue;

	for (startScan = 0; startScan < (size - 1); startScan++)
	{
		minIndex = startScan;
		minValue = array[startScan];

		for (int index = startScan + 1; index < size; index++)
		{
			comparisons_selection++;
			if (array[index] < minValue)
			{
				minValue = array[index];
				minIndex = index;
			}
		}
		interchanges_selection++;
		array[minIndex] = array[startScan];
		array[startScan] = minValue;
	}
}
Topic archived. No new replies allowed.