asked on

Trouble with Selection Sort and populating an array in reverse

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

rajeev_devin

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

rajeev_devin

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

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

rajeev_devin

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

warriorfan808

ASKER

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.

jkr

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;;

}

warriorfan808

ASKER

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;
}

ASKER CERTIFIED SOLUTION

jkr

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial