Sorting and Searching.

Pages: 123
I need help with the linear search and bubble sort binary sort. I have zero clue how to do that.

Write a program that lets the user enter a charge account number. Be sure to include comments throughout your code where appropriate. The program should determine if the number is valid by checking for it in the following list of valid account numbers:

8149420
5333174
3080098
6755963
9526981
4449539
9387197
5104726
2931356
4282637
1750219
6086650
3164838
2419590
4578589
9718904
6749941
2545408

Initialize a one-dimensional array with these values. Then use a simple linear search to locate the number entered by the user. If the user enters a number that is in the array, the program should display a message indicating that the account number is valid. If the user enters a number not in the array, the program should display a message indicating it is invalid.

Next, using the same one-dimensional array, use a bubble-sort to put the array in order and perform a binary search to locate the number entered by the user. If the user enters a number that is in the array, the program should display a message indicating that the account number is valid. If the user enters a number not in the array, the program should display a message indicating it is invalid.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
  //Charles Blackwell CIS 211 Module 9
#include <iostream>
using namespace std;
//Function Prototype
const int number_list = 18;
bool searcharray(int entered_number, int lookup_number[number_list]);
int main()
{
	int account_number[] = { 8149420, 5333174, 3080098, 6755963, 9526981,
4449539, 9387197, 5104726, 2931356, 4282637, 1750219, 6086650,
3164838, 2419590, 4578589, 9718904, 6749941, 2545408 };
	int chargenumber = 0;
	bool find = true;
	cout << "                                   *Charge Account Validation*         " << endl;
	//input of account number
	cout << "_______________________________________________________________________" << endl;
	cout << "Please enter the account number: " << endl;
	cin >> chargenumber;
	//If/else statement based on if the account number is right or wrong
	find = searcharray(chargenumber, account_number);
	if (find==true)
		cout << "\nCharge " << chargenumber << " is a valid number" << endl;
	else
		cout << "\nCharge " << chargenumber << " is not a valid number" << endl;
	return 0;
}
//For loop
bool searcharray( int entered_number, int lookup_number[number_list] )
{
	bool find = false;

	for (int i = 0; i < number_list; i++)
	{
		if (entered_number == lookup_number[i])
			return true;
	}
	return false;


}
I have zero clue how to do that.
So, and what are expecting now?

I would suggest that you search the internet for bubble sort and binary search. That you should provide enough clues to start with.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>

void const display(int* anArray, int aSize)
{
    for(int i = 0; i < aSize; i++)
        std::cout << anArray[i] << ' ';
    
    std::cout << '\n';
    return;
}

void bubbleSort(int* aArray, int aSize)
{
    int temp{0};
    
    for(int j = 0; j < aSize - 1; j++)
    {
        for(int i = 0; i < aSize - 1; i++)
        {
            if ( aArray[i + 1] < aArray[i] )
            {
                temp = aArray[i + 1];
                aArray[i + 1] = aArray[i];
                aArray[i] = temp;
                
                display(aArray, aSize); // TO SEE THE SWAPS
            }
        }
    }
    return;
}

int main()
{
    int array[]{-23, 75, 60, 50, 30, 20, 10, 5, 60, 30, 10, 50, 5, 75, -2};
    int limit = sizeof(array)/sizeof(int);
    
    display(array, limit);
    bubbleSort(array, limit);
    display(array, limit);
    
    return 0;
}
Last edited on
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <utility>
#include <iterator>

// algorithm: https://en.wikipedia.org/wiki/Bubble_sort#Implementation
// visualisation: https://en.wikipedia.org/wiki/File:Bubble-sort-example-300px.gif

// bubble once: go through the array once,
// comparing adjacent elements and swapping them if they are out of order.
// at the end of a bubble, the largest item in the array would bubble up to the last place
// return true if at least one swap was performed
// return false if no swap was done (if the array was already in sorted order)
bool bubble( int array[], int n )
{
    bool swapped = false ;

    for( int i = 1 ; i < n ; ++i ) // go through the array once
    {
        if( array[i-1] > array[i] ) // if two adjacent elements are out of order.
        {
            // swap them
            // https://en.cppreference.com/w/cpp/algorithm/swap
            using std::swap ;
            swap( array[i-1], array[i] ) ;
            swapped = true ; // and indicate that something was swapped
        }
    }

   return swapped ; // true if at least one swap was performed
}

// sort an array containing n elements
void bubble_sort( int array[], int n )
{
    // keep bubbling till the array is fully sorted
    // note: with each bubble, the largest item in the array of n elements
    //       rises to the last place. the next bubble deals with the remaining n-1 elements
    while( bubble( array, n ) ) --n ;
}

// TO DO: read up on binary search: https://en.wikipedia.org/wiki/Binary_search_algorithm#Algorithm
// TO DO: implement binary search
bool bsearch( const int sorted_array[], int array_size, int value_to_search_for ) ;

int main() // simple test driver
{
    int test[] { 9, 8, 3, 6, 5, 2, 7, 4, 1, 0 } ;

    // std::size https://en.cppreference.com/w/cpp/iterator/size
    const auto n = std::size(test) ; // there are n items in the test array
    bubble_sort( test, n ) ;

    for( int v : test ) std::cout << v << ' ' ;
    std::cout << '\n' ;
}

http://coliru.stacked-crooked.com/a/9d28acf36709642a
there are many online studies of both algorithms that show the actual data moving in an animation to explain the algorithm. Watching that will show you what needs doing, then you should be able to code it.

There are of course the above and other working code online but you should understand and write it yourself. The binary search specifically ... if you do not understand how to code this from scratch, you will quickly become behind as the idea is the backbone of multiple concepts.
Hello All,

I'm a beginner and while I appreciate the code above you provided I am still confused and unsure how to add the searches I need for my assignment and the code I posted.

binary search won't work without sorted data. so the first thing to do is sort the data, debug and test that its working.

Did you watch an animation? A simple bubble sort is just a nested (2 deep) loop over the data, swapping it over and over until its done. If you watched, it should be pretty easy to cook up loops to do this -- give it a try and post what you come up with, and what the output of your sort looks like (even if its wrong, post it and ask).

The code is even in this thread, multiple times.
Also, do you need more basic help? We get that you are a beginner, but we don't know what is tripping you up.
Last edited on
I watched it but don't understand. I get a error at line 44

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

//Charles Blackwell CIS 211 Module 9
#include <iostream>
using namespace std;
//Function Prototype
const int number_list = 18;
bool searcharray(int entered_number, int lookup_number[number_list]);
int main()
{
	int account_number[] = { 8149420, 5333174, 3080098, 6755963, 9526981,
4449539, 9387197, 5104726, 2931356, 4282637, 1750219, 6086650,
3164838, 2419590, 4578589, 9718904, 6749941, 2545408 };
	int chargenumber = 0;
	bool find = true;
	cout << "                                   *Charge Account Validation*         " << endl;
	//input of account number
	cout << "_______________________________________________________________________" << endl;
	cout << "Please enter the account number: " << endl;
	cin >> chargenumber;
	//If/else statement based on if the account number is right or wrong
	find = searcharray(chargenumber, account_number);
	if (find == true)
		cout << "\nCharge " << chargenumber << " is a valid number" << endl;
	else
		cout << "\nCharge " << chargenumber << " is not a valid number" << endl;
	return 0;
}
//For loop
bool searcharray(int entered_number, int lookup_number[number_list])
{
	bool find = false;

	for (int i = 0; i < number_list; i++)
	{
		if (entered_number == lookup_number[i])
			return true;
	}
	return false;


}

void bublesort(int lookup_number[number_list], int enter_number)
{
	int k, i, temp, flag;
	for (k = 1; k < enter_number; k++)
	{
		flag = 0;
		for (i = 0; i < enter_number - k; i++)
		{
			if (lookup_number[number_list] > lookup_number[i + 1])
			{
				temp = lookup_number[number_list];
				lookup_number[number_list] = lookup_number[i + 1];
				lookup_number[i + 1] = temp;
				flag = 1;
			}
		}
		if (flag == 0)
			break;
	}
Indeed. 61:2: error: expected '}' at end of input
you did not close the bubblesort function with an ending } at least in the posted code.

after fixing that, it ran for me:

Please enter the account number:
2545408

Charge 2545408 is a valid number

But, you did not call your sort, and your search is not binary. Please do what we ask if you want to get through this... please do these 2 things:

- sort the array, using your sort function, from main (call the function)
- print out the sorted array, and verify that it works.
Last edited on
im confused. what line does the } go ?
cblack618 is a proven troll.
Stop feeding it.
Let it die.
I am not a troll. I am posting legitimate trying to get help. What you don't understand is that IM A BEGINNER. I KNOW THE PURE BASICS.
@jonnin

1. How do i fix the line 61.2 error ?

2. How do i call my sort and make it binary ?
The sort is a separate and totally different operation to a binary search.

PS certainly troll-like and I should know :)
Last edited on
Can you help me do that ?
No. Do what jlborges wrote for your TODO list and look it up.
Rude. I have looked it up. But still dont understand. Do you think I'm on here asking help just for my health ?
Stop bickering or you’ll upset NambyPamby.

Hope this helps.
Mr Rude
Can someone please help me finish this assignment
Can you read these instructions and tell me what I need ? I was told I was missing a binary search and bubble sort


Initialize a one-dimensional array with these values. Then use a simple linear search to locate the number entered by the user. If the user enters a number that is in the array, the program should display a message indicating that the account number is valid. If the user enters a number not in the array, the program should display a message indicating it is invalid.

Next, using the same one-dimensional array, use a bubble-sort to put the array in order and perform a binary search to locate the number entered by the user. If the user enters a number that is in the array, the program should display a message indicating that the account number is valid. If the user enters a number not in the array, the program should display a message indicating it is invalid.
Pages: 123