This is a discussion on bubble sort not sorting numbers in order. within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by laserlight hmm... Code: After sorting... 1 5 13 24 35 37 44 72 96 98 I mean ...
What is your current code?
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
Instead of having i <= k as the condition for the inner loop, use i < k.Originally Posted by rushhour
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)