Solved

# Trouble with Selection Sort and populating an array in reverse

Posted on 2006-05-04
224 Views
I'm trying to automatically populate an array in reverse to get the worste case scenario and time the selection sort algorithm.  I was able to get the best case scenario to work fine, but it seems that populating an array in reverse is kind of confusing.  I'm pretty sure I'm doing it right, but it keeps inserting only the value of, "n" in all the indexes of my array A[];
I've tried it a lot of different ways.  This is my current attempt.  My others involved a for loop, which I believe should have worked too.

inputs:: the user is asked how large of an array do they want to populate, then that number is defined as n.
int reverse = 0;
int A[10000];

while(n>0)
{
A[reverse]= n;
//std::cout << i <<" "<< n << "\n";//testing the order
reverse++;
n=n-1;
}//end of for loop

I can post more of my code, if you think that will help
0
Question by:warriorfan808

LVL 12

Expert Comment

I have modified your code a little bit

int n = 10;
int reverse = 0;
int A[10000];

while(n >= 0)
{
A[reverse]= n-1;
std::cout << reverse <<" "<< n << "\n";//testing the order
reverse++;
n = n-1;
}//end of for loop
0

LVL 12

Expert Comment

>> while(n>0)
this hould be n>=0

>> A[reverse]= n;
This should be n-1
0

LVL 12

Expert Comment

>> int n = 10;
In the above code fragment I have hard coded n = 10. You can take this as input.
0

LVL 1

Author Comment

sorry, didn't put specifics.  I only wanted to test from n to 1

1,2,3,4,.....n-2, n-1, n

I figured that n>0 would work because it would put value 0 into the index 100 of A[];

why is it that it should be n-1?

would that just assign the value of, "if n = 100', 99 to index 0?

I'll try it though and see what happens.
0

LVL 86

Expert Comment

You could just

#include <iostream>
using namespace std;

void main () {

int A[10000];
int n = 10000;
for ( int i = 0; i < 10000; i++, n--) A[i] = n;

// just to check the array for it's contents again
for ( int j = 0; j < 10000; j++) cout << A[j] << endl;;

}
0

LVL 1

Author Comment

I wanted the user to have the option to select the array size.  I did this because I wanted to compare the time it takes to run 10, 100, 1000, 10000 in sequencial order and then compare to 10, 100, 1000, 10000 in decremental order.

#include <iostream>
#include <time.h>

void swap(int &m, int &n);

int main()
{

int n;
//int* A = new int[n];
int A[200000];
int response;
//int T[100000];
int reverse = 0;

clock_t start, end, total;
clock_t totaln = 0;
start = clock() ;
//end = 0;

std::cout<<"What array size will you be testing"<<std::endl;
std::cin >> n;

std::cout<<"Would how would you like the array to be populated?"<<std::endl;
std::cout<<"reverse order: example 100, 99, 98"<<std::endl;
std::cout<<"or regular order: example 1, 2, 3 "<<std::endl;
std::cout<<"type 1 for regular or 2 for reverse"<<std::endl;
std::cin >> response;

for(int count =0; count <= 100; count++)//this for loop is to run this program 100 times
{
if(n > 1000)
{
count = 100;
}//this if is used if the number is larger than 1000.  In this case, we wouldn't have to run 100 times.

if( response == 1)//if the response is 1, then we populate the array in sequencial order
{
for (int i =1; i <=n; ++i)
{
A[i]= i;

}//end of for loop
}
if (response == 2)//if the response is 2, then we populate the array in desequencial order
{
while(n>=0)
{
A[reverse]= n-1;
//std::cout << i <<" "<< n << "\n";//testing the order
reverse++;

}//end of for loop

}
for(int i= 0; i<(n-1);i++)//start of selection sort
{
int min = i;
for(int j = i+1; j<n; j++)
{
if(A[j] < A[min])
{
min = j;

}//end of for loop

}//end of for loop

if (min > i)
{
swap(A[i], A[min]);//swap function
}//end of if

}//end of for loop
for (int i = 0; i <= n; i++)
{
std::cout << i << " " << A[i] << std::endl;
}//end of for loop

end = clock() ;

total = end - start;      //this total will be for numbers larger than 1000

totaln = total + totaln;      //this total will be used and then divided by 100, for numbers less than a thousand

//delete[] A;

}
totaln = totaln/100;
if(n < 1000)
{
printf( "time = %u\n", totaln ) ;
}

else
{
printf( "time = %u\n", total ) ;

}

return 0;
}//end of main
void swap(int &x, int &y)
{
int temp;

temp = x;
x = y;
y = temp;
}

0

LVL 86

Accepted Solution

Not a big deal, just make that

if (response == 2)//if the response is 2, then we populate the array in desequencial order
{
int m = n; // temp. storage that we can decrement without changing 'n'
for ( int i = 0; i < n; i++, m--) A[i] = m;
}
0

## Featured Post

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.