See problem 3.4 on page 112. You are going to implement the odd-even sort in the C language not java. You don't need to do any of his instructions concerning listing 3.1. The task will be to sort a file using a single command line file. HOWEVER, I don't want to see the whole sorted file, so the output will simply be any of the ints in the sorted file (that I may specify--see below) when sorted from lowest to highest). So I should be able to query and REPEATEDLY ask for a number in a certain index until I ask for -1 which indicates an invalid index and the program should stop. So, for example, if the index specified is 3 then I want the number in index 3 (which will be the 4th smallest number). Next, I might specify 500 or whatever. Eventually I specify -1 and the program stops. For THIS program I am am going to use gcc on Osprey with a single command line file that will have a very large number of random ints (at least 1000, perhaps significantly more and they might be positive, negative , or zero). The very first number in the file, however, is not actual data, but rather it specifies the number of numbers after it. So you will want to calloc an array to store the data so that the array is the correct size. You can google calloc is you have never used it or you can find some examples in the C book or my website under one of the tabs for C. DO NOT STORE THE VERY FIRST NUMBER IN THE ARRAY. ONLY STORE THE NUMBERS AFTER THAT AND OF COURSE THE SMALLEST NUMBER WILL EVENTUALLY BE STORED IN INDEX 0 (NOT 1). BE CAREFUL WHEN PROGRAMMING AS THERE APPEARS TO BE AN ERROR IN HIS LOGIC. I BELIEVE HE IGNORES THE NUMBER IN INDEX 0. The number of ints on a single line is unknown; there might be just one or there might be many. They will be separated by "white space"...blanks, tabs, or newlines. 

Writing programs that solve the Programming Projects helps to solidi of the material and demonstrates how the chapter's concepts are a (As noted in the Introduction, qualified instructors may obtain completed to the Programming Projects on the publisher's Web site.) 3.1 In the bubbleSort.java program (Listing 3.1) and the BubbleSort V applet, the in index always goes from left to right, finding the larges carrying it toward out on the right. Modify the bubbleSort() method bidirectional. This means the in index will first carry the largest item to right as before, but when it reaches out, it will reverse and carry th item from right to left. You'll need two outer indexes, one on the right out) and another on the left. op item and so that it's from left e smallest (the ) m 3.2 Add a method called median() to the ArrayIns class in the insertsort.java program (Listing 3.3). This method should return the median value in the array. (Recall that in a group of numbers half are larger than the median and half are smaller.) Do it the easy way 3.3 To the insertsort.java program (Listing 3.3), add a method called noDups() that removes duplicates from a previously sorted array without disrupting the order. (You can use the insertionsort() method to sort the data, or you can simpl e main() to insert the data in sorted order.) One can imagine schemes in which all the items from the place where a duplicate was discovered to the end of the array would be shifted down one space every time a duplicat discovered, but this would lead to slow O(N2) time, at least when there were a lot of duplicates. In your algorithm, make sure no item is moved more than once, no matter how many duplicates there are. This will give you an algo- rithm with O(N) time 3.4 Another simple sort is the odd-even sort. The idea is to repeatedly make two passes through the array. On the first pass you look at all the pairs of items a[j] and a[], where j is odd (j = 1, 3, 5, ). If their key values are out of order, you swap them. On the second pass you do the same for all the even values (j 2, 4, 6, ...). You do these two passes repeatedly until the array sorted. Replace the bubbleSort() method in bubbleSort.java (Listing 3.1) witi an oddEvenSort() method. Make sure it works for varying a You'll need to figure out how many times to do the two passes mounts of data. where a The odd-even sort is actually useful in a multiprocessing environm separate processor can operate on each odd pair simultaneously ach even pair. Because the odd pairs are independent of each othe can be checked-and swapped, if necessary-by a different proc makes for a very fast sort. usly and then on cessor. This