bubble sort not sorting numbers in order.

Originally Posted by laserlight

hmm...

Code:

After sorting...
   1   5  13  24  35  37  44  72  96  98

I mean 35 before sorting, not after sorting.

What is your current code?

Originally Posted by laserlight

What is your current code?

Code:

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

typedef int intArray[];
void generate(intArray nums, int size, int low, int high);
void bubSort(intArray nums, int size);
void displayNums(intArray nums, int size);
void display(int n);
bool notInOrder(int a, int b);
void swap(int& a, int& b);

int main()
{
  const int MAX_SIZE = 5000; // arbitrary
  int numbers[MAX_SIZE];
  int howMany;

  cout << "How many numbers to sort? ";
  cin >> howMany;

  if(howMany > MAX_SIZE)
    {
      howMany = MAX_SIZE;
    }

  generate(numbers, howMany, 0, 999);
  cout << "Numbers generated..." << endl;
  displayNums(numbers, howMany);
  cout << endl;
  bubSort(numbers, howMany);
  cout << "After sorting..." << endl;
  displayNums(numbers, howMany);
  cout << endl;
}

void generate(intArray nums, int size, int low, int high)
{
  int n, i = 0;
  do
    {
      n = (rand() + time(0)) % 100;
      if(n >= low && n <= high)
	{
	  nums[i] = n;
	  i++;
	}
    }while (i <= size);
}

void bubSort(intArray nums, int size)
{
  for(int k = size-1; k >= 0; k--)
    {
      for(int i = 0; i <= k; i++)
	{
	  if(notInOrder(nums[i],nums[i+1]))
	    {
	      swap(nums[i],nums[i+1]);
	    }
	}
    }
}

void displayNums(intArray nums, int size)
{
  for(int s = 0; s < size; s++)
    {
      cout.width(4);
      cout << nums[s];
      if(s != 0 && s%15 == 0)
	{
	  cout << endl;
	}
    }
}

bool notInOrder(int a, int b)
{
  return (a > b);
}

void swap(int& a, int& b)
{
  int temp;
  temp = a;
  a = b;
  b = temp;
}

You have an array out of bounds access in bubSort(). On the first iteration of the outer loop, k = size-1. However, the inner loop loops until and including the iteration where i = k. In that iteration, nums[i+1] is nums[k+1]. Since k = size - 1, that means that nums[k+1] is nums[size-1+1] which is nums[size], hence the array is accessed out of bounds.

Originally Posted by laserlight

You have an array out of bounds access in bubSort(). On the first iteration of the outer loop, k = size-1. However, the inner loop loops until and including the iteration where i = k. In that iteration, nums[i+1] is nums[k+1]. Since k = size - 1, that means that nums[k+1] is nums[size-1+1] which is nums[size], hence the array is accessed out of bounds.

So how would I go about correcting it? Sorry to be of bother but it has been a long day trying to get this working, and now more problems seem to appear as I go on seems like I will never make the program work fully! So I hope you can help.

Originally Posted by rushhour

So how would I go about correcting it?

Instead of having i <= k as the condition for the inner loop, use i < k.

Originally Posted by laserlight

Instead of having i <= k as the condition for the inner loop, use i < k.

Thank you very much for helping me. Seemed simple now that I have thought about it.