Bubble sorting and finding a location of a number in array

Question

NinjaLink -2 Posting Pro in Training

17 Years Ago

I am trying to do the [B]bubble sort[/B] to make my numbers in the array go from smallest to highest. Afterwards, I want to use the [B]SeqOrderedSearch[/B] to find the location of the number in the array. If the number is not found, i will have to state it is not found.

The program runs fine. I'm just not getting the numbers I want.

Sample:

Original Array: 22, 59, 29, 11, 77, 4, 9, 82, 39, 81
Sorting array...
Sorted Array: 4, 9, 11, 22, 29, 39, 59, 77, 81, 82

Enter a number to search the array: 77
77 was found in location #8

Note: if the user selects 42 (42 is not in the array), it will then be "42 was NOT found"

Here is my code:

#include <iostream>
#include <iomanip>

using namespace std;

void printArray (int numbers[]);
void bubblesort (int numbers[], int length);
int seqOrderedSearch (int numbers[], int length, int searchItem);


int main ()
{

    int numbers[] = {22,59,29,11,77,4,9,82,39,81};
    int loc;
    int searchItem;

printArray(numbers);
bubblesort(numbers,10);
loc = seqOrderedSearch(numbers,10,searchItem);   


 cout<<"Enter a number to search the array: "<<endl;
 cin>>searchItem;

cout<<searchItem<<" is found in location #"<<loc<<endl;

system ("PAUSE");
return 0;
}



void printArray (int numbers[])
{

     cout<<"Original array...."<<endl;

for (int i = 0; i<10; i++)
{
    cout<<numbers[i]<<" ";



}
    cout<<endl;
    cout<<"Sorting array...."<<endl;

}



void bubblesort (int numbers[], int length)
{

 int temp;
 int iteration;

 for (iteration = 1; iteration < length; iteration++)
 {
     for (int i = 0; i < length - iteration; i++)
     {
         if (numbers[i] > numbers[i+1])
         {
             temp = numbers[i];
             numbers[i] = numbers[i+1];
             numbers[i + 1] = temp;
         }     
     }
 }      


}



int seqOrderedSearch (int numbers[], int length, int searchItem)
{

  cout<<endl;

  int loc;
  bool found = false;


  for (loc = 0; loc < length; loc++)
  {
      if (numbers[loc] >= searchItem)
      {
        found = true;
        break;
      }

      if (found)
      if (numbers[loc] == searchItem)
         return loc;
      else
       cout<<searchItem<<" was NOT found"<<endl;
  }
}

c++

Edited 13 Years Ago by Reverend Jim because: Fixed formatting

4 Contributors
8 Replies
200 Views
15 Hours Discussion Span
Latest Post 17 Years Ago Latest Post by Ancient Dragon

Dani AI

Generated 7 Months Ago

Brief summary of the problems and fixes (building on and ): the crash you see happens because the search result is used as an array index without checking it (so a -1 or an out-of-range index dereferences memory). The ordered-sequential search logic is also incorrect: you should return as soon as you find the item, stop early when the current array value exceeds the target, and return a sentinel (e.g. -1) when not found. Don’t print "found/not found" from inside the search routine — let main() handle messaging. Print the sorted array after the sort (in main or via a printing helper) rather than inside the inner loop of the sort.

Correct ordered sequential search (returns index or -1):

int orderedSearch(const int a[], int n, int target) {
    for (int i = 0; i < n; ++i) {
        if (a[i] == target) return i;    // found
        if (a[i] > target) break;        // no need to continue in sorted array
    }
    return -1; // not found
}

Correct bubble-sort pattern and where to print the result:

void bubbleSort(int a[], int n) {
    for (int pass = 0; pass < n - 1; ++pass)
        for (int i = 0; i < n - pass - 1; ++i)
            if (a[i] > a[i+1]) std::swap(a[i], a[i+1]);
}
// After calling bubbleSort(numbers, n) in main, print the array once:
cout << "Sorted array: ";
for (int i = 0; i < n; ++i) cout << numbers[i] << (i+1<n ? ", " : "\n");

Check the search return in main before indexing:

int pos = orderedSearch(numbers, n, key);
if (pos != -1)
    cout << key << " is found in location #" << (pos + 1) << '\n'; // +1 for human-friendly index
else
    cout << key << " was NOT found\n";

Extra tips: avoid using system("PAUSE"), decide whether you want 0-based or 1-based reporting (adjust print accordingly), and test edge cases such as searching for values less than the min and greater than the max. This addresses the crash you saw and keeps responsibilities (search vs. I/O) clean.

All 8 Replies

dougy83 74 Posting Whiz in Training

17 Years Ago

Line 20 should be moved to after line 24: you want to let the user enter the search value before you call the search function.

line 86: remove this line - the break statement would quit the loop; before you get to report the location

the seqOrderedSearch function should return a value if the item is not found, e.g. -1; generally you would check the return value to decide whether you would display "item x found at loc" or "item x not found", and remove the cout statement from the seqOrderedSearch function

Ancient Dragon 5,243 Achieved Level 70

17 Years Ago

line 20 is in the wrong place -- move it down to line 25, when the variable search_item is known.\

[edit]^^^ he beat me to it :) [/edit]

Reply to this topic

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.

NinjaLink -2 Posting Pro in Training · Answer 1 · 2008-10-12T08:35:05+00:00

Thanks for the replys guys.

I have a couple more questions..

1) Where do I put my cout statement to display my sorted array in the "bubblesort" function? I tried putting it in several places, but it didn't work.

2) How and where do I put a cout statement saying "<number> is not found" when the user insert a number that is not in the array?

Here is my updated code:

#include <iostream>
#include <iomanip>

using namespace std;

void printArray (int numbers[]);
void bubblesort (int numbers[], int length);
int seqOrderedSearch (int numbers[], int length, int searchItem);


int main ()
{

    int numbers[] = {22,59,29,11,77,4,9,82,39,81};
    int loc;
    int searchItem;

printArray(numbers);
bubblesort(numbers,10);


 cout<<endl;
 cout<<"Enter a number to search the array: "<<endl;
 cin>>searchItem;

loc = seqOrderedSearch(numbers,10,searchItem);

cout<<searchItem<<" is found in location #"<<loc<<endl;


system ("PAUSE");
return 0;
}


void printArray (int numbers[])
{

     cout<<"Original array....";

for (int i = 0; i<10; i++)
{
    cout<<numbers[i]<<" ";



}
    cout<<endl;
    cout<<"Sorting array...."<<endl;
    cout<<"Sorted array...";

}
void bubblesort (int numbers[], int length)
{

 int temp;

 for (int i = 0; i < length; i++)
 {
     for (int j = 0; j < length - i; j++)
     {
         if (numbers[i] < numbers[i+1])
         {
             temp = numbers[i];
             numbers[i] = numbers[i+1];
             numbers[i + 1] = temp;
         }     
     }
 }      


}


int seqOrderedSearch (int numbers[], int length, int searchItem)
{

  cout<<endl;

  int loc;
  bool found = false;
  int NOT;


  for (loc = 0; loc < length; loc++)
  {
      if (numbers[loc] >= searchItem)
      {
        found = true;
      }

      if (found)
      if (numbers[loc] == searchItem)
         return loc;
      else
       return -1;
  }
}

Ancient Dragon 5,243 Achieved Level 70 Team Colleague Featured Poster · Answer 2 · 2008-10-12T08:48:12+00:00

Ancient Dragon 5,243 Achieved Level 70

17 Years Ago

1) after line 19

2) Change line 28 to test for return value of line 26

NinjaLink -2 Posting Pro in Training · Answer 3 · 2008-10-12T09:15:23+00:00

[QUOTE=Ancient Dragon;710574]1) after line 19

2) Change line 28 to test for return value of line 26[/QUOTE]

Thanks.

The only problem is #2 though.

I am trying an "if" statement in main so I correct the problem....The problem is that i can't figure out how to write the "cout" statements outside of the loop, so the cout statement can only once. Please help!

Here is the code in main:

int main ()
{

    int numbers[] = {22,59,29,11,77,4,9,82,39,81};
    int loc;
    int searchItem;
    int length = 10;

printArray(numbers);
bubblesort(numbers,10);
for (int i = 0; i < length; i++)
 {
 cout<<numbers[i]<<" ";
 }



 cout<<endl;
 cout<<"Enter a number to search the array: "<<endl;
 cin>>searchItem;

loc = seqOrderedSearch(numbers,10,searchItem);

for (int i = 0; i < length; i++)
{
    if (numbers[i] == searchItem)
    {
 cout<<searchItem<<" is found in location #"<<loc<<endl;
    }
    if (numbers[i] != searchItem)
    {
  cout<<searchItem<<" was NOT found"<<endl;
    }
}

system ("PAUSE");
return 0;
}

NinjaLink -2 Posting Pro in Training · Answer 4 · 2008-10-12T09:58:00+00:00

I have an update.

I got the "if" statement working for the cout statements on whether the number is found or not. The question I now have is.......

when I enter a number above "82" which is the largest number in the array, it gives me an error and the program shuts down...All numbers that I enter 82 and under shows that it is either found or not. Is that suppose to happen? If so, I am done with this program!

int main ()
{
    
    int numbers[] = {22,59,29,11,77,4,9,82,39,81};
    int loc;
    int searchItem;
    int length = 10;
    bool found = false;
    
printArray(numbers);
bubblesort(numbers,10);
for (int i = 0; i < length; i++)
 {
 cout<<numbers[i]<<" ";
 }



 cout<<endl;
 cout<<"Enter a number to search the array: "<<endl;
 cin>>searchItem;
 
loc = seqOrderedSearch(numbers,10,searchItem);

if (numbers[loc] == searchItem)
cout<<searchItem<<" is found in location #"<<loc<<endl;
else
cout<<searchItem<<" was NOT found"<<endl;



    
system ("PAUSE");
return 0;
}

Sci@phy 97 Posting Whiz in Training · Answer 5 · 2008-10-12T14:49:42+00:00

Sci@phy 97 Posting Whiz in Training

17 Years Ago

It shouldn't happen, but this code isn't giving anything

Ancient Dragon 5,243 Achieved Level 70 Team Colleague Featured Poster · Answer 6 · 2008-10-12T17:13:29+00:00

Your program works fine for me.

Sci: His last post was only main() -- the rest is in the origianl post.

Bubble sorting and finding a location of a number in array

Dani AI

Recommended Answers Collapse Answers

All 8 Replies

Recommended Answers