C++

Forum

 
Sorting with random numbers

CodingIsHard17 (106)
Using the rand () function, fill 5 arrays of integers with the same 10 random numbers. These numbers should be values between 1-100. The arrays should hold 10 integers and named; bubbleArray, selectionArray, insertionArray, quickArray, and mergeArray.

2. You should use the: a. Bubble sort function to sort the bubbleArray b. Selection sort function to sort the selectionArray c. Insertion sort function to sort the insertionArray d. Quick sort function to sort the quickArray e. Merge sort to sort the mergeArray Each unsorted array should be outputted to a file name Assignment2Results followed by the sorted version of the array and the time taken to sort the array to the same file.

Any help with modifying the selection sort to actually run? Also did I implement it in the correct spot?

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
 
#include <iostream>
#include <math.h> 
#include <stdlib.h>
#include <ctime>   

using namespace std;

// sorting using bubblesort
void bubbleSort(int bubbleArray[], int numb)
{
     int temp;
     for(int pass=0; pass<numb; pass++)
        for(int i=0; i<numb-1; i++)
        {
            if(bubbleArray[i] > bubbleArray[i+1])
           {
               temp = bubbleArray[i];
               bubbleArray[i]= bubbleArray[i+1];
               bubbleArray[i+1]= temp;
                            
           }
    }
     return;
}


void selectionSort(int selectionArray[], int size)
{
	
	int startScan, minIndex, minValue;
	
	for(startScan =0; startScan < (size-1); startScan++)
	{
		minIndex = startScan;
		minValue = selectionArray(startScan);
		for (int index = startScan + 1; index < size; index++)
		{
			if (selectionArray(index) < minValue)
			{
				minValue= selectionArray[index];
				minIndex = index;
			}
		}
		selectionArray[minIndex]= selectionArray[startScan];
		selectionArray[startScan]= minValue;
	}
}



int main()
{
int i, j, n=10, temp;
int bubbleArray [n];
int selectionArray [n];
int insertionArray [n];
int quickArray [n];
int mergeArray [n];

srand (time(NULL));

cout << "Random list of bubbleArray: ";
for (i = 0; i < 10; i++)
{
    int value = rand() % 100; // Random from 1 through 100 ; allows for all arrays to generate the same random numbers
    bubbleArray [i] = value;
    selectionArray [i] = value;
    insertionArray [i] = value;
    quickArray [i] = value;
    mergeArray [i] = value;
    
    
    cout << bubbleArray [i] << " ";

}


cout << "\nRandom list of selectionArray: ";

for (i = 0; i < 10; i++)
{
    cout << selectionArray [i] << " ";
}


cout << "\nRandom list of insertionArray: ";
for (i = 0; i < 10; i++)
{
    cout << insertionArray [i] << " ";
}


cout << "\nRandom list of quickArray: ";
for (i = 0; i < 10; i++)
{
    cout << quickArray [i] << " ";
}


cout << "\nRandom list of mergeArray: ";
for (i = 0; i < 10; i++)
{
    cout << mergeArray [i] << " ";
}


bubbleSort(bubbleArray, i);
cout << endl << "\nThis is the list after being sorted by the bubble sort method: ";
 
// loop sorting random numbers by bubble sort
for (i = 0; i < 10; i++)
{ 
cout << bubbleArray[i] << " ";
}

selectionSort(selectionArray, size)
cout << endl << "\nThis is the list after being sorted by the selection sort method: ";

// loop that sorts using selection sort
for(startScan =0; startScan < (size-1); startScan++)
{
    cout << selectionArray[i] << " ";
}

system("pause");
return 0;
}
Duthomhas (13208)
Lines 44 and 45 are the failure. Look at what you are doing to one if the numbers.

I recommend you write yourself a swap( int& x, int& y ) function. You will reuse it in most of these algorithms.
CodingIsHard17 (106)
Like this? It doesn't run of course so I would like to know if you can provide guidance on the topic.

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
 
#include <iostream>
#include <math.h> 
#include <stdlib.h>
#include <ctime>   

using namespace std;

// sorting using bubblesort
void bubbleSort(int bubbleArray[], int numb)
{
     int temp;
     for(int pass=0; pass<numb; pass++)
        for(int i=0; i<numb-1; i++)
        {
            if(bubbleArray[i] > bubbleArray[i+1])
           {
               temp = bubbleArray[i];
               bubbleArray[i]= bubbleArray[i+1];
               bubbleArray[i+1]= temp;
                            
           }
    }
     return;
}


void selectionSort(int selectionArray[], int n)
{
    int min;
    for(int k = 0; k < n - 1; k++)
    {
        min = k;
        for(int j = k+1; j < n; j++)
        {
            if(selectionArray[j] < selectionArray[min])
            {
                min = j;
            }
        }
        
        swap(&selectionArray[min], &selectionArray[k]);
    }
}
    return;
}
  


int main()
{
int i, j, n=10, temp;
int bubbleArray [n];
int selectionArray [n];
int insertionArray [n];
int quickArray [n];
int mergeArray [n];

srand (time(NULL));

cout << "Random list of bubbleArray: ";
for (i = 0; i < 10; i++)
{
    int value = rand() % 100; // Random from 1 through 100 ; allows for all arrays to generate the same random numbers
    bubbleArray [i] = value;
    selectionArray [i] = value;
    insertionArray [i] = value;
    quickArray [i] = value;
    mergeArray [i] = value;
    
    
    cout << bubbleArray [i] << " ";

}


cout << "\nRandom list of selectionArray: ";

for (i = 0; i < 10; i++)
{
    cout << selectionArray [i] << " ";
}


cout << "\nRandom list of insertionArray: ";
for (i = 0; i < 10; i++)
{
    cout << insertionArray [i] << " ";
}


cout << "\nRandom list of quickArray: ";
for (i = 0; i < 10; i++)
{
    cout << quickArray [i] << " ";
}


cout << "\nRandom list of mergeArray: ";
for (i = 0; i < 10; i++)
{
    cout << mergeArray [i] << " ";
}


bubbleSort(bubbleArray, i);
cout << endl << "\nThis is the list after being sorted by the bubble sort method: ";
 
// loop sorting random numbers by bubble sort
for (i = 0; i < 10; i++)
{ 
cout << bubbleArray[i] << " ";
}

selectionSort(selectionArray, n)
cout << endl << "\nThis is the list after being sorted by the selection sort method: ";

void printArray(int selectionArray[], int size)
{
    for (int i = 0; i < size; i++)
    cout << selectionArray[i] << " ";
}

system("pause");
return 0;
}
Duthomhas (13208)
First trick: crank up your compiler warnings and take care of them, one by one, until things compile correctly. (You have been advised this before.)

I do not know what you are using to edit your code, but find yourself a code editor that understands C++ with syntax highlighting and automatic indenting.

I have cleaned it up for 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
 
#include <algorithm>  // for std::swap, if you aren't going to write your own swap function
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

// sorting using bubblesort
void bubbleSort(int bubbleArray[], int numb)
{
     int temp;
     for(int pass=0; pass<numb; pass++)
        for(int i=0; i<numb-1; i++)
        {
            if(bubbleArray[i] > bubbleArray[i+1])
           {
               temp = bubbleArray[i];
               bubbleArray[i]= bubbleArray[i+1];
               bubbleArray[i+1]= temp;

           }
    }
     return;
}


void selectionSort(int selectionArray[], int n)
{
    int min;
    for(int k = 0; k < n - 1; k++)
    {
        min = k;
        for(int j = k+1; j < n; j++)
        {
            if(selectionArray[j] < selectionArray[min])
            {
                min = j;
            }
        }

        swap(selectionArray[min], selectionArray[k]);
    }
}


void printArray(int array[], int size)
{
    for (int i = 0; i < size; i++)
        cout << array[i] << " ";
}


int main()
{
    constexpr int n=10;
    int i, j, temp;
    int bubbleArray [n];
    int selectionArray [n];
    int insertionArray [n];
    int quickArray [n];
    int mergeArray [n];

    srand ((unsigned)time(NULL));

    cout << "Random list of bubbleArray:    ";
    for (i = 0; i < 10; i++)
    {
        int value = rand() % 100; // Random from 1 through 100 ; allows for all arrays to generate the same random numbers
        bubbleArray [i] = value;
        selectionArray [i] = value;
        insertionArray [i] = value;
        quickArray [i] = value;
        mergeArray [i] = value;


        cout << bubbleArray [i] << " ";

    }


    cout << "\nRandom list of selectionArray: ";
    printArray(selectionArray,n);


    cout << "\nRandom list of insertionArray: ";
    printArray(insertionArray,n);


    cout << "\nRandom list of quickArray:     ";
    printArray(quickArray,n);


    cout << "\nRandom list of mergeArray:     ";
    printArray(mergeArray,n);


    bubbleSort(bubbleArray, i);
    cout << endl << "\nThis is the list after being sorted by the bubble sort method:\n";
    printArray(bubbleArray,n);


    selectionSort(selectionArray, n);
    cout << endl << "\nThis is the list after being sorted by the selection sort method:\n";
    printArray(selectionArray,n);


//    system("pause");
    return 0;
}

Insertion sort is almost as simple as selection sort.
Quicksort and mergesort are basic sorts, but they are tricky to implement correctly.

For quicksort, the hardest part is the partion function.
Make life easy for yourself and just choose the first element in a section as the pivot. Remember to use swap() to move elements towards the ends.

For mergesort, there are options. I recommend a bottom-up mergesort for ease. Then you only need to loop over the array by twos, then fours, then eights, etc, until you run out of partitions. Additionally, you can allocate the entire block of additional memory one time, at the toplevel invocation, and just reuse it with all your calls to the merge function.

Good luck!

[edit]
I take it back on the mergesort. Do a top-down sort. It keeps life easiest. The basic algorithm:

  merge_sort( array, first, last ):
    if (last - first < 2) return
    mid = (last - first) / 2 + first
    merge_sort( array, first, mid )
    merge_sort( array, mid, last )
    merge( array, first, mid, last )

The merge() function there is where you need to spend time. In my own implementation I added another argument to the functions for the additional space you need to do the merge. My main merge_sort function looks like:

1
2
3
4
5
6
 
void merge_sort( int array[], int n )
{
  int* temp = new int[n/2+1];
  merge_sort( array, 0, n, temp );
  delete[] temp;
}

Good luck. Seriously.
Last edited on
CodingIsHard17 (106)
Hey thanks. I try to focus on indentation but then I get too riled up with the actual code writing. Would you be able to help me figure out why my time calculation of how long it takes to sort keeps reading 0 seconds?

For example:

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
 
mergeSort(mergeArray, 0, i-1);
myfile << endl << "- This is the list after being sorted by the merge sort method: ";

	for (i = 0; i < 10; i++)	// loop for sorting rand numbs by merge sort
	{
    	myfile << mergeArray[i] << " ";
	}


myfile << "\n" << endl;

{
	clock_t start = clock(); 

	int mergeArray[n];
		
	for(int i = 0; i < 10; i++)
	{
		myfile << mergeArray[i]<<"\t";
	}
	myfile<<endl;
 
	clock_t finish = clock();
	double doneTime = float(finish-start)/CLOCKS_PER_SEC; 
	myfile << "- You took " << fixed << doneTime << setprecision(8) << " seconds\n";
}
lastchance (6980)
time calculation of how long it takes to sort

The code you present above is measuring how long it takes to write an (illegally defined, non-initialised) array of 10 numbers to file.


keeps reading 0 seconds

Modern computers are pretty quick. It doesn't take long to write 10 numbers to file.
CodingIsHard17 (106)
So that is correct the way I have it?

Modern computers are pretty quick. It doesn't take long to write 10 numbers to file.


It also says 0 seconds when I do it with 1000 numbers.
jonnin (11437)
When doing very small amounts of data you may want to count the CPU clock cycles instead of seconds.

clock is almost as old as I am and was built for machines that were quite slow. It cannot measure tiny amounts of time.

this is what I use:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
struct hrtimer
{
 high_resolution_clock::time_point s; 
 duration<double> time_span;
 void start(){s = high_resolution_clock::now();}
 double stop()
 {    
   time_span = duration_cast<duration<double>>( high_resolution_clock::now() - s);
   return time_span.count();
 }
};

hrtimer h;
h.start();
//sort( //whatever here
tm = h.stop(); 
cout << tm << endl;

Last edited on
CodingIsHard17 (106)
1
2
3
4
5
6
7
8
9
10
11
 
struct hrtimer
{
high_resolution_clock::time_point s;
duration<double> time_span;
void start(){s = high_resolution_clock::now();}
double stop()
{
time_span = duration_cast<duration<double>>( high_resolution_clock::now() - s);
return time_span.count();
}
};


How would I put that in my snippet two posts above? I have five different arrays so when I try switching things around keeps reading that I wrote it somewhere else and that I am duplicating it.
jonnin (11437)
... it defines a timer, put it right above main and use it in main as the little example below the struct shows.
just reuse the timer, h.start / h.stop pairs and print the time.

its the same pattern as clock... get time and save it, get time again and subtract it, and convert it to a useful value and print... just higher resolution than clock. You don't even need the struct, it just packages it up rather than repeat the same code over and over or have loose local functions.

I think all it needs is
#include <chrono>
if you get any missing stuff complaints or 'does not define a type' or the like I can check that.
Last edited on
Topic archived. No new replies allowed.