PASS Week 3/31

PROBLEM #1

Create a program that will declare an array of size 100 that contains random values between 1 and 999.

	1) Create a user defined function that will load that array with 100 random integers.
	2) Create a second function that prints the array to the screen 10 numbers per line.
	   Use a minimum width specifier to ensure the numbers line up (For ease of reading/testing).

The main function should ONLY CONTAIN 5 LINES OF CODE: srand, the array declaration, two function calls, and a return statement.
You must use srand() in main. Sample output and Skeleton code provided below.

Sample Output:

945 832 578 934  24  75 617 471 262  95
726 536 997 657 252 858 943 752 435   4
542 762 369 571 891 325 495 103 815 838
453 479 389  32 414 412 824 749 882  86
843 609 340 840 266 592 417 927 344 852
931 604 614 300 175 505 343 388 607 159
226 778 637 614 528 769  27 352 518 627
156 362 236 496 920 220 806 338 148 868
190 797 472 522 815 365  27 159 472 352
 36 697 848 672  31 377 442 775 447 678




/*** SKELETON CODE ***/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAXSZ 100 //Defined constant for size of array

void LoadArray(int[], int); //First parameter is array, second is size of array
void PrintArray(int[], int); //First parameter is array, second is size of array


int main(void)
{
	srand(Time(NULL));

	int ary[MAXSZ]; //Declare Array of size 100 (Variable MAXSZ is equal to 100)

	LoadArray(ary, MAXSZ);
	PrintArray(ary, MAXSZ);

	return 0;
}//end main

/*** LOAD ARRAY FUNCTION GOES HERE ***/

/*** PRINT ARRAY FUNCTION GOES HERE ***/














Problem #2

Using the program you created in Problem #1, do the following:

	1) Create a third function that will prompt the user for an integer value between
	   1 and 999, and search for that number. (Sequential Search). The 2 parameters
	   needed for this function are the array, and the size of the array.
	2) Put your user prompts for the value to search for INSIDE the function. DON'T
	   prompt the user in main.
	3) Call that function AFTER the array is loaded.

If the value is found, print out the index location of the item and continue to search to
the end of the array. (There may be more than one occurrence of the same value in
the array, try to accommodate for repeats in your program).

Sample output (Value found):

Enter a value to be searched for: 5
Number 5 found at index 91.



Sample output (Value not found):

Enter a value to be searched for: 5
Number not found



Sample output (Multiple values found):

Enter a value to be searched for: 99
Number 99 found at index 5.
Number 99 found at index 77.















Problem #3

Using the program you made in Problem #2, do the following:

	1) Implement the Bubble Sort function in your program from Problem #2. This can be called
	   in main to sort the array from least to greatest. THIS FUNCTION IS GIVEN TO YOU, PROVIDED BELOW.
	2) Now change main to call the functions in this order: load the array, print the array, sort the array,
       and then print out the array again.
	3) Comment out your search function call from problem #2.
	4) Run the program and make sure it sorted all of the items. If it isn't sorted, check your functions & calls.
	   If the first or last few values aren't sorted but the rest is, check your loop condition or iterator.

Visualizing how the bubble sort can be difficult, try drawing it out on paper with your array
step-by-step and see what it is doing. Refer to modules, teammates, or me for help.
There are also good videos on YouTube that show the bubble sort in action.


Sample Output:

391 198 748 560 255 641 660 547 825 624
851 747 772 469 974 893 323 520 461 571
410 348 828 949 667 931  10 173 860 148
733 969 345 481 529 318 122 907 865 947
251 716 694  23 185 387 634 226 625  96
516  35 162  63 984 547 994 993 719 854
141 452 542 485 651  72 803 773 697 387
439 947 103 133 689   6 239 323 950 863
137 466 617  18 528 601 283 241 313 721
813 454 173 356 657 543 146 179 316 842

  6  10  18  23  35  63  72  96 103 122
133 137 141 146 148 162 173 173 179 185
198 226 239 241 251 255 283 313 316 318
323 323 345 348 356 387 387 391 410 439
452 454 461 466 469 481 485 516 520 528
529 542 543 547 547 560 571 601 617 624
625 634 641 651 657 660 667 689 694 697
716 719 721 733 747 748 772 773 803 813
825 828 842 851 854 860 863 865 893 907
931 947 947 949 950 969 974 984 993 994




HERE IS THE CODE FOR BubbleSort TO ADD TO YOUR PROGRAM:

//Function prototype (Put this above main)
void BubbleSort (int[], int);

//Function definition (Put this below main)
	//Parameter "aryIn" is your Array
	//Parameter "last" is the end index in your array
void BubbleSort(int aryIn[],int last)
{
	int temp = 0;
	for(int current = 0; current < last; current++)
	{
		for(int walker = last; walker > current; walker--)
		{
			if(aryIn[walker] < aryIn[walker -1])
			{
				temp = aryIn[walker];
				aryIn[walker] = aryIn[walker - 1];
				aryIn[walker - 1] = temp;

			}//end if
		}//end inner for
	}//end outer for

	return;
}//end bubbleSort


















Problem #4

Using your program from Problem #3, do the following:

	1) Add a new search function to your program that performs a binary search.
	   THIS FUNCTION IS GIVEN TO YOU, PROVIDED BELOW.
	2) In main: comment out your sequential search function call (if you haven't already),
	   then load the array, bubble sort the array, then search the array with your new binary search function.
	3) The search function should return the index location of the item found.

Recall that the item could be at index 0, so you may need to check that.
You will need to alter how you test the results in main. Same as the bubble sort,
if you have trouble visualizing it refer to your teammates, modules, me, or the internet.
There are a lot of good videos that visualize the process.

Sample Output:

389 777 677 792 509 558 170 969 104 649
947  93 587 388 623 432 227 928 804 869
445 109 722 440 473 369 427 797 406 260
852 513 755 529 305 265 806 194 952 909
842 619 721 148   7 344 580 952 990 103
821 154 211 262 593 683 631  21 200 755
998 770 269 753  19 292 736 824 485 408
452  47  27 173 194  33 235 773 703 226
595 524 379 805 505 972 208 136 711 407
609 709 177 877 462 195 170 917 737 373

Enter a value to be searched for: 7
Number found at index 0




Here is the function for the Binary Search to add to your program:

//Function prototype (Put this above main)
int BinarySearch (int[], int, int);

//Function definition (Put this below main)
	//This function only works on sorted arrays!
	//Parameter "list" is your array
	//Parameter "end" is the last index of your array
	//Parameter "target" is the number you are searching for
	//THIS FUNCTION RETURNS THE INDEX LOCATION OF THE NUMBER YOU SEARCH FOR

int BinarySearch(int list[], int end, int target)
{
	int location = 0, first = 0, mid, last = end;

	while(first <= last)
	{
		mid = (first + last) /2;//Find the middle

		if(target > list[mid])
			first = mid + 1; //Look in the upper half of list
		else if (target < list[mid])
			last = mid - 1; //Look in the lower half of list
		else
			first = last + 1;//Found the item force quit
	}//end while

	if(list[mid] == target)//What if item is at index 0?
		return mid;
	else
		return -1;
}//end BinarySearch