C++

Forum

 
bubble, insertion, selection sort program

givememyusername (3)
my out put currently is 

lab03

the original array has been reset to:
 20 40 10 30 
SORTING -  Bubble Sort Ascending - O(n2) algorithm
 20 10 40 30 


the original array has been reset to:
 20 40 10 30
SORTING -  Selection Sort Asccending - O(n2) algorithm
 10 40 20 30 
 10 20 40 30 
 10 20 30 40 

the original array has been reset to:
 20 40 10 30
SORTING -  Insertion Sort Acending - O(n2) algorithm
 10 40 20 30 
 10 20 40 30 
 10 20 30 40 

DONE -Thomas kim

I need my output to look like this

lab03

the original array has been reset to:
 20 40 10 30 
SORTING -  Bubble Sort Ascending - O(n2) algorithm
 20 10 30 40 
 20 10 30 40 
 10 20 30 40 

the original array has been reset to:
 20 40 10 30
SORTING -  Selection Sort Asccending - O(n2) algorithm
 10 40 20 30 
 10 20 40 30 
 10 20 30 40 

the original array has been reset to:
 20 40 10 30
SORTING -  Insertion Sort Acending - O(n2) algorithm
 20 40 10 30 
 20 40 40 30
 20 20 40 30 
 10 20 40 30 
 10 20 40 40 
 10 20 30 40 
DONE -Thomas kim

help would be greatly appreciated. thank you! 
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
131
132
133
 
// Thomas Kim
// 2/19/14
#include <iostream>
#include <iomanip>
using namespace std;

 

// Prototypes 
void reset (const int startNum[], int num [], int size); 
void displayIntArray (const int num[], int size); 
void BubbleSort(int num [], int size); 
void SelectionSort(int num [], int size); 
void insertionSort(int num [], int size);



int main ()
{
  
	const int SIZE = 4;
	const int start_num [SIZE] = {20, 40, 10, 30};
	int numbers [SIZE]; 
 
	cout << "Lab03 \n"; 
	
	reset (start_num, numbers,  SIZE);
	cout <<"\nSORTING -  Bubble Sort Ascending - O(n2) algorithm\n";
	BubbleSort (numbers, SIZE);
	
	reset ( start_num, numbers,  SIZE);
    cout<<"\n\nSORTING -  Selection Sort Asccending - O(n2) algorithm\n";
	SelectionSort (numbers, SIZE);
	
	reset ( start_num, numbers,  SIZE);
	cout<<"\n\nSORTING -  Insertion Sort Acending - O(n2) algorithm\n";
	insertionSort (numbers,  SIZE);

	cout<<"\n\nDONE -Thomas Kim\n";
	cout <<endl <<endl;
	
	system("pause");
	return 0;
}


//
void reset (const int startNum[], int num[], int size)
{
	cout << endl << "The original array has been reset to:" << endl;
	for (int index = 0; index < size; index++)
	{
	num[index] = startNum[index];
	}
	for (int index = 0; index < size; index++)
	{
	cout << setw(5) << num[index];
	}
	cout << endl;
}
//
void displayIntArray (const int num[], int size)
{
	for (int index = 0; index < size; index++)
	{
	cout << setw(5) << num[index];
	}
}

//
void BubbleSort(int num [], int size)
{
	bool swap;
	int temp;

	do
	{
		swap = false;
		for (int count = 0; count < (size - 1); count++)
		{	
			if (num[count] > num [count + 1])
			{
				temp = num[count];
				num[count] = num[count +1];
				num[count +1] = temp;
				swap = true;				
			}
		}
		displayIntArray (num, size);
		cout << endl;
	} while (swap);
}

//
void SelectionSort(int num [], int size)
{
	int startscan, minindex, minvalue;

	for (startscan = 0; startscan < (size - 1); startscan++) 
	{
		minindex = startscan;
		minvalue = num[startscan];
		for(int index = startscan + 1; index < size; index++)
		{
			if (num[index] < minvalue)
			{
				minvalue = num[index];
				minindex = index;
			}
		}
		num[minindex] = num[startscan];
		num[startscan] = minvalue;
		displayIntArray (num, size);
		cout << endl;
	}
}

//
void insertionSort(int num [], int size)
{
		for (int i = 1; i < size; i++)
		{
		int j;
		int current = num[i];
			for (j = i - 1; j >= 0 && num[j] > current; j--)
			{
			num[j+1]=num[j];
			}
		num[j+1]=current;
		displayIntArray (num, size);
		cout << endl;
		}
}
Smac89 (1727)
Umm, you don't want your insertion sort output to look like this:
1
2
3
4
5
6
 
20 40 10 30 
20 40 40 30
20 20 40 30 
10 20 40 30 
10 20 40 40 
10 20 30 40


Not only is this not O(N2), but it does not look like the process an insertion sort algorithm will take to sort the array. Also, random duplicates?? Take a look at line 127

Your bubblesort algorithm looks correct, so I can't figure out how it is producing the output you have described
givememyusername (3)
hmm yea that is strange i dunno why my professor wanted that for the output maybe he goofed up. i dont see any duplicates? also to clarify am i outputting each instance of change correctly? i feel like im not showing each step of the sort.
Smac89 (1727)
This is what your output should look like:
Lab03

The original array has been reset to:
   20   40   10   30
SORTING -  Bubble Sort Ascending - O(n2) algorithm
   20   10   30   40
   10   20   30   40
   10   20   30   40

The original array has been reset to:
   20   40   10   30
SORTING -  Selection Sort Asccending - O(n2) algorithm
   10   40   20   30
   10   20   40   30
   10   20   30   40

The original array has been reset to:
   20   40   10   30
SORTING -  Insertion Sort Acending - O(n2) algorithm
   20   40   10   30
   10   20   40   30
   10   20   30   40

DONE - ****** ***
Topic archived. No new replies allowed.