How to make an online Generator? What Program?

binary search program help c programming assignment

• I need a C master to roll his wisdom and skill into my skull so i can pass this very difficult online course : ) assignment: Add a binary search to the implementation of QuickSort that we have been working on. The code is in Code/Quick_Sort. Your finished product should generate an array of random integers (first command line arg is the number of integers to be generated) and sort them using QuickSort and then search the array for any number of integers that are entered on the command line, writing an appropriate message to standard output for each. EXAMPLE: a command line like this... Quick 100 8 31 59 should give output like this... 8 is not in the list 31 is not in the list 59 is in the list Have fun! ------------more assignment notes The functions In the directory Code/Quick_Sort there are several source files and some other files yo need to look at and/or use. They are, in no particular order,: * makefile - The makefile for the existing version of the code * makefile.binsearch - The makefile you will use after writing your binary search function * Partition.c - The function that does the partition (no kidding!) * Sort.c - The function that calls Partition( ) and then makes the recursive calls to itself * swap.c - switches 2 items in the list * Quick.c - This is actually a sort of "dummy" function. This layer allowed me to interchange sorting algorithms using the same code. * main.c - driver that generates a random list of ints and then calls the sort function * timming - table of data showing how different sorting algorithms compare Please make sure you look carefully at all this code. It is only a total of about 30 lines of code, but it is packed. Just be sure you understand each line and even each character! I'm going to show the Partition( ) and Sort( ) functions here, because I need to make a few points, but the rest is pretty simple and I leave it up to you to ask if there is anything you aren't clear on. The source code The source for Partition( ) which picks a pivot item and splits the list: int Partition(int *l,int low,int high) { void swap(int,int,int*); int i,pivotloc; int pivotkey; swap(low,(low+high)/2,l); pivotkey = l[low]; pivotloc = low; for (i=low+1;i<=high;i++) if (l[i] < pivotkey) swap(++pivotloc,i,l); swap(low,pivotloc,l); return (pivotloc); } First, you call swap( ) to get the pivot item from the middle of the list. Then we initialize "pivotkey" to the value of the pivot item and "pivotloc" to the index in the list where the pivot item is. You will notice that each time we find an item that belongs before the pivotkey, we swap it to the location pointed to by pivotloc. Each time this switch happens we incrament pivotloc so that pivotloc always points to the first item that does not go before the pivotkey. Then after the for loop ends, we swap the pivot item back to the middle of the list, at pivotloc, so that that item is where it belongs and the list has been split in two. You can see this in detail in the "walk through" in the next section. The source for Sort( ) which calls partition and then calls itself to sort the 2 parts of the list that Partition( ) creates: void Sort(int *l,int low,int high) { int Partition(int*,int,int); int pivotloc; if (low < high) { pivotloc = Partition(l,low,high); Sort(l,low,pivotloc-1); Sort(l,pivotloc+1,high); } } Notice that this function is really very simple, conceptually. All it does is get the pivot location from Partition( ) and then call itself to sort each half of the list. Aside from the whole recursive thing, there really is nothing to it. QuickSort algorithim "walk through" You need to do most of the "walk through" yourself. All of the code is very straight forward, even the Sort( ) function with the recursive call, except for the Partition( ) function. We are going to take a list with 10 items and walk through the first call to Partition( ). Once you see one pass of Partition( ) you can apply it yourself to the rest of the run of the program. the Partition( ) function Lets use an array called "data". In the code the array is called "l"(ell), but the "l"(ell) looks too much like a "1"(one), so I'm going with "data". :) Suppose the array is filled as follows: begin walk through we have low = 0 and high = 9 so then middle = 4 and after swapping the middle item with the first item we get: swap partition to beginning Now the for loop will start "i" at 1 and go through 9 and if data[i] is less than pivotkey, we make the swap. Now with i = 1 and data[i] = 54 and pivotkey = 55 data[i] is less than pivotkey so we make the swap. first swap in partition Notice the list looks the same? That is because we incrament pivotloc before we do the swap, and in this case pivotloc = 1 and so does "i" so we "swapped" the 54 with itself. Now we have i = 2 and data[i] = 60 and pivotkey = 55 so data[i] is not less than pivotkey so we don’t swap. Now we have i = 3 and data[i] = 62 and pivotkey = 55 so data[i] is not less than pivotkey so we don’t swap. Now we have i = 4 and data[i] = 58 and pivotkey = 55 so data[i] is not less than pivotkey so we don’t swap. Continuing, we have i = 5 and data[i] = 51 and pivotkey = 55 so data[i] is less than pivotkey so we make the swap. another swap in partition Notice that pivotloc was incramented to 2 before we made the swap so that data[i] was swapped with a value that is larger than pivotkey. This is important, because we know that we do not have to check that item to see if it is less than pivotkey, because we already checked it. Now we have i = 6 and data[i] = 47 and pivotkey = 55 so data[i] is less than pivotkey so we incrament pivotloc to 3 and make the swap. another swap in partition For i = 7 and i = 8 we don't need to swap, but for i = 9 we have data[i] = 53 and pivotkey = 55 so data[i] is less than pivotkey so we incrament pivotloc to 4 and make the swap. another swap in partition Now we have to put the pivotkey in the place where it belongs. pivotloc is 4, which is the last location occupied by a value less than the pivotkey, so since all the values after that one are greater than the pivotkey we make one last swap, swapping data[low] with data[pivotloc]. last swap in partition Now Partition( ) returns pivotloc so that Sort( ) can call itself for the 2 "halfs" of the list, like this: Sort(low,pivotloc-1,data); Sort(pivotloc+1,high,data); Do a complete walk through! Make your own list of about 10 items (or use the one I have here) and do a complete walk through. You should make a picture like the one from the "QuickSort algorithim" section in these notes, except yours will have numbers in it. Don't worry if several of the pivot items that get picked are not in the middle of the list, with a short list, you could get several "bad" ones. The point is to walk through the code and try to keep track of where you are with calls to Sort( ). The best thing to do is to get a pile of scrap paper and each time you call Sort( ) in your walk through, make a new sheet of paper with all the variable values on it. Your "stack" of Sort( ) calls will mimic the actual stack on the system. Each time you finish an instance of Sort( ) simply take it off the pile. The paper now on top is the instance of Sort( ) that you should be in. Good luck and email me questions or problems. program given w/ assignment; [root@win186821wks out]# more * :::::::::::::: binary_search.c :::::::::::::: #define MAX 11 main() { int top,bottom,middle,i,key; int data[]={31,45,57,88,143,201,204,327,328,414,499}; printf("sorted list:\n"); for (i=0;i<MAX;i++) printf("%d\n",data[i]); printf("Enter search key: "); scanf("%d",&key); top=0; bottom=MAX-1; middle=(top+bottom)/2; do{ if (data[middle]<key) top=middle+1; else bottom=middle; middle=(top+bottom)/2; }while(top<bottom); if (data[middle]==key) printf("%d was found at location %d\n",key,middle); else printf("%d was not found\n",key); } :::::::::::::: main.c :::::::::::::: /*************************************************/ /* main driver for Quick-Sort implementation */ /* This program will create an array of ints */ /* using a random number generator, then print */ /* the array, then sort it with a Quick-Sort */ /* algorithm, then print it again. */ /*************************************************/ #include <math.h> main(int c,char **v) { void Quick(int,int*); int *list; int count,i; if (c==1) {printf("Usage: Quick list_size\n");exit();} /* use the first command line argument as the number of elements to create and sort */ count=atoi(v[1]); /* allocate space for the array */ list=(int *)malloc(count*sizeof(int)); /* generate the array of random ints... use %count so that each number is the remainder when you divide by count. Thus the biggest number you can get in your array is count-1 */ for(i=0;i<count;i++) list[i]=random(i)%count; /* print - sort - print */ for(i=0;i<count;i++) printf("%d\n",list[i]); Quick(count,list); for(i=0;i<count;i++) printf("%d\n",list[i]); } :::::::::::::: makefile :::::::::::::: Quick: Quick.o main.o Partition.o Sort.o swap.o cc Quick.o main.o Partition.o Sort.o swap.o -o Quick -lm Quick.o: Quick.c cc -c Quick.c main.o: main.c cc -c main.c Partition.o: Partition.c cc -c Partition.c Sort.o: Sort.c cc -c Sort.c swap.o: swap.c cc -c swap.c :::::::::::::: makefile.binsearch :::::::::::::: Quick: Quick.o main.o Partition.o Sort.o swap.o binsearch.o cc Quick.o main.o Partition.o Sort.o swap.o binsearch.o -o Quick -lm Quick.o: Quick.c cc -c Quick.c main.o: main.c cc -c main.c Partition.o: Partition.c cc -c Partition.c Sort.o: Sort.c cc -c Sort.c swap.o: swap.c cc -c swap.c binsearch.o: binsearch.c cc -c binsearch.c :::::::::::::: Partition.c :::::::::::::: int Partition(int *l,int low,int high) { void swap(int,int,int*); int i,pivotloc; int pivotkey; swap(low,(low+high)/2,l); pivotkey = l[low]; pivotloc = low; for (i=low+1;i<=high;i++) if (l[i] < pivotkey) swap(++pivotloc,i,l); swap(low,pivotloc,l); return (pivotloc); } :::::::::::::: Quick.c :::::::::::::: void Quick(int n,int *list) { void Sort(int*,int,int); Sort(list,0,n-1); } :::::::::::::: Sort.c :::::::::::::: void Sort(int *l,int low,int high) { int Partition(int*,int,int); int pivotloc; if (low < high) { pivotloc = Partition(l,low,high); Sort(l,low,pivotloc-1); Sort(l,pivotloc+1,high); } } :::::::::::::: swap.c :::::::::::::: void swap(int i,int j,int *l) { int tmp; tmp = l[i]; l[i] = l[j]; l[j] = tmp; } :::::::::::::: timming :::::::::::::: n selection insertion shell quick -------------------------------------------------- 1000 1.9 1.5 1.0 1.0 2000 5.0 4.1 2.1 2.0 3000 10.1 7.8 3.1 3.1 5000 26.9 19.0 5.4 5.2 10000 110.5 73.8 10.9 10.4 50000 ----- 1647.7 54.1 52.7 -------------------------------------------------- 1647.7 seconds is approx 27.5 minutes

• Answer:

  Hello derekwtp-ga, I've completed code. I will only post the files that have changed. There were three main changes. 1) Handle the command-line arguments for what numbers to search for. To do that I allocated an array and then pulled the numbers from the argv array in main(). 2) Write a binary search function to look for one number in a sorted list. I wrote a recursive version of that function. It is a bit cluttered because it does not assume its input array has an even number of values. Still, the basic idea is: a) check the middle value to see if it is the number we want. b) if not, look at the half of the array to that number's left. c) if it wasn't in that half, look in the numbers in the right half. 3) print out the result of each search. I hope that helps you. And again, don't be afraid to tip your trusty researcher. dogbite-ga :::::::::::::: makefile :::::::::::::: Quick: Quick.o main.o Partition.o Sort.o swap.o BinarySearch.o cc Quick.o main.o Partition.o Sort.o swap.o BinarySearch.o -o Quick -lm Quick.o: Quick.c cc -c Quick.c main.o: main.c cc -c main.c Partition.o: Partition.c cc -c Partition.c Sort.o: Sort.c cc -c Sort.c swap.o: swap.c cc -c swap.c BinarySearch.o: BinarySearch.c cc -c BinarySearch.c :::::::::::::: BinarySearch.c :::::::::::::: int BinarySearch(int numberToFind,int *list, int size) { int middleIndex = (size / 2); int recursiveResult; /* base case(s) */ if (size <= 0) { return 0; /* false */ } else if (size == 1) { return (list[0] == numberToFind); } else { /* check the middle */ if (list[middleIndex] == numberToFind) { return 1; } else { /* if size is odd */ if ((size % 2) == 1) { recursiveResult = BinarySearch(numberToFind, list, size/2); /* if we didn't find it on the "left" side */ if (recursiveResult != 1) { /* search the "right" side */ recursiveResult = BinarySearch(numberToFind, list + size/2 + 1, size/2 ); return recursiveResult; } else { /* we found it on the "left" side */ return recursiveResult; } } /* size is even */ else { recursiveResult = BinarySearch(numberToFind, list, size/2); /* if we didn't find it on the "left" side */ if (recursiveResult != 1) { /* search the "right" side */ if (size > 2) { recursiveResult = BinarySearch(numberToFind, list + size/2 + 1, size /2 - 1); } return recursiveResult; } else { /* we found it on the "left" side */ return recursiveResult; } } } } } :::::::::::::: main.c :::::::::::::: /*************************************************/ /* main driver for Quick-Sort implementation */ /* This program will create an array of ints */ /* using a random number generator, then print */ /* the array, then sort it with a Quick-Sort */ /* algorithm, then print it again. */ /*************************************************/ #include <math.h> main(int c,char **v) { void Quick(int,int*); int BinarySearch(int, int*, int ); int *list; int *searchlist; int searchlistsize; int count,i; if (c==1) {printf("Usage: Quick list_size\n");exit();} /* use the first command line argument as the number of elements to create and sort */ count=atoi(v[1]); searchlistsize = c - 2; /* allocate space for the array */ list=(int *)malloc(count*sizeof(int)); /*allocate space for the search list */ searchlist = (int *) malloc(searchlistsize*sizeof(int)); /* populate the list with values from commandline */ for(i = 0; i < searchlistsize; i++) { searchlist[i] = atoi(v[i+2]); } /* generate the array of random ints... use %count so that each number is the remainder when you divide by count. Thus the biggest number you can get in your array is count-1 */ for(i=0;i<count;i++) list[i]=random(i)%count; /* print - sort - print */ /* for(i=0;i<count;i++) printf("%d\n",list[i]); */ Quick(count,list); /* for(i=0;i<count;i++) printf("%d\n",list[i]); */ for (i = 0; i < searchlistsize; i++) { if (BinarySearch(searchlist[i], list, count) == 1) { printf("%d is in the list\n", searchlist[i]); } else { printf("%d is not in the list\n", searchlist[i]); } } }