Writing programs that solve the Programming Projects helps to solidi of the mate

Question

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

Explanation / Answer

#include<stdio.h>
#include<stdlib.h>
// Pointer to store numbers
int *arr;
// Read in the parts file and returns the length
int readFile()
{
// File pointer
FILE *fptr;
// No for number of numbers
// c for counter variable
int no, c;
// Open the file for reading
fptr = fopen("NUMBERS.txt", "r");

// Check that it opened properly
if (fptr == NULL)
{
printf("Cannot open file ");
exit(0);
}// End of if condition
// Reads number of numbers in the file
fscanf(fptr, "%d", &no);

// Dynamically allocates memory to pointer arr
arr = (int *) calloc(no, sizeof(int));
// Loops no times
for(c = 0; c < no; c++)
// Reads each number and stores it in array
fscanf(fptr, "%d", &arr[c]);
// Returns the length of the numbers
return no;
}// End of function

// Function to display numbers
void display(int no)
{
int c;
// Loops no times
for(c = 0; c < no; c++)
// Displays each number
printf("%4d, ", arr[c]);
}// End of function

// Function for insertion sort
void insertionSort(int no)
{
int x, key, y;
// Loops no times
for (x = 1; x < no; x++)
{
// Stores i index position data in key
key = arr[x];
// Stores x minus one as y value
y = x - 1;

/*
Move elements of arr[0..x - 1], that are greater than key,
to one position ahead of their current position
*/
while (y >= 0 && arr[y] > key)
{
// Stores arr y index position value at arr y next index position
arr[y + 1] = arr[y];
// Decrease the y value by one
y = y - 1;
}// End of while
// Stores the key value at arr y plus one index position
arr[y + 1] = key;
}// End of for loop
}// End of function

// main function
int main()
{
// To store the numbers of number in file
int no;
// Calls the function to read numbers and stores the length
no = readFile();
// Calls the function to displays the numbers before sorting
printf(" Before sorting: ");
display(no);
// Calls the function for sorting
insertionSort(no);
// Calls the function to displays the numbers after sorting
printf(" After sorting: ");
display(no);
}// End of main function

Sample Run:

Before sorting: 10, 20, 11, 22, 45, 78, 5, 3, 7, 18, 28, 1, 0, 5, 8, 51, 32, 80, 9, 27,
After sorting: 0, 1, 3, 5, 5, 7, 8, 9, 10, 11, 18, 20, 22, 27, 28, 32, 45, 51, 78, 80,

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.