Overview: I am trying to write a program that generates an array of randomly generated integers, and sorts them as the array is being generated. I've just used 7 elements in the following example, as it's easier to check for errors that way.

Code:

#include <iostream>
#include <ctime>
#include <cstdlib>

using namespace std;

void sortArray(int array[], int size) {
      int i, j, tmp;
      for (i = 1; i < size; i++) {
            j = i;
            while (j > 0 && array[j - 1] > array[j]) {
                  tmp = array[j];
                  array[j] = array[j - 1];
                  array[j - 1] = tmp;
                  j--;
            }
      }
}

int main()
{
    int nums[7];
    srand(time(NULL)); //seeding with the system time
    for (int i=0; i<7; i++){
        nums[i]=rand();
        sortArray(nums, i);
    }
    for (int t=0; t<7; t++) cout << nums[t] << " ";
    return 0;
}

Output: It appears to sort the numbers into ascending order, but the last number outputted is not where it should be - it isn't the highest number. I'm sure it's something simple but I can't spot it. Here's an example output:
1906 4950 15321 .... 29951 10910

Thank you.

Just an update - I think I have solved the problem (although if somebody could still explain to me, because I'm not sure WHY I've solved it :) )

I changed line 26 above from sortArray(nums, i); to sortArray(nums, i+1); and it appears to sort the list (whether it is correct or not, I'm not sure).

Why does this appear to make a difference?

Thanks again :)

#include <iostream>
#include <ctime>
#include <cstdlib>

using namespace std;

void sortArray(int array[], int size) {
      int i, j, tmp;
      for (i = 1; i < size; i++) {
            j = i;
            while (j > 0 && array[j - 1] > array[j]) {
                  tmp = array[j];
                  array[j] = array[j - 1];
                  array[j - 1] = tmp;
                  j--;
            }
      }
}

int main()
{
    int nums[7];
    srand(time(NULL)); //seeding with the system time
    for (int i=0; i<7; i++){
        nums[i]=rand();        
    }
    sortArray(nums, sizeof(nums)/sizeof(int)); //move the function out of the loop
    for (int t=0; t<7; t++) cout << nums[t] << " ";
    return 0;
}

These sort of problems are much more amenable to understanding if you first write out your algorithm either mathematically, or in many cases, in plain language pseudo-code. Example for an insertion sort (your final code is not using an insertion sort, because it is sorting after the array is generated), you generate a number, and insert it into the list. The insert function will find the correct position and if it is not at the bottom, move everything below where it goes down one element, and put the new member there. So, in plain language pseudo-code:

main:
while not done
   generate number N
   insert N in list
   check if done
end while

insert N:
    # First do empty list optimization
   if list size == 0
       list[0] = N
       list size = 1
   else
       for i = 0, while insert not done and i < list size, i = i + 1
           if list[i] > N # we found the spot
               move list from i to list size - 1 down one element
               list[i] = N
               insert done = true
           else if i == list size - 1  # We are at end of list, N goes here
               list[list size] = N
               list size = list size + 1
               insert done = true  # this is redundant because the increment at the
                            # top of the loop will kick us out, but say what you mean
                            # anyway, it will eliminate an entire class of bugs
           end if
       end for
   end if

I'm leaving the move list down function to you... :-)

Thank you guys, that was extremely helpful! :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.