Problem: While the testing of a program with a random data set is quite common,

Question

Problem: While the testing of a program with a random data set is quite common, it is sometimes useful to
create special data sets with which one would test a program. For this particular assignment you will create a data set of integers, maximum set size of 25, that is nearly sorted in an ascending order. Replicate the development of the nearly sorted ascending output as seen in the examples that follow.

Example Execution #1:
Enter data #1 or -1 to exit: 5
Enter data #2 or -1 to exit: 3
Enter data #3 or -1 to exit: 4
Enter data #4 or -1 to exit: 2
Enter data #5 or -1 to exit: 6
Enter data #6 or -1 to exit: 1
Enter data #7 or -1 to exit: 0
Enter data #8 or -1 to exit: 8
Enter data #9 or -1 to exit: -1

Original Data: 5 3 4 2 6 1 0 8
Final Data: 0 1 2 3 4 5 8 6

Example Execution #2:
Enter data #1 or -1 to exit: 5
Enter data #2 or -1 to exit: 5
Enter data #3 or -1 to exit: 5
Enter data #4 or -1 to exit: 5
Enter data #5 or -1 to exit: 4
Enter data #6 or -1 to exit: 5
Enter data #7 or -1 to exit: 5
Enter data #8 or -1 to exit: -1

Original Data: 5 5 5 5 4 5 5
Final Data: 5 4 5 5 5 5 5

Example Execution #3:
Enter data #1 or -1 to exit: 2
Enter data #2 or -1 to exit: 8
Enter data #3 or -1 to exit: 5
Enter data #4 or -1 to exit: 1
Enter data #5 or -1 to exit: 10
Enter data #6 or -1 to exit: 5
Enter data #7 or -1 to exit: 9
Enter data #8 or -1 to exit: 9
Enter data #9 or -1 to exit: 3
Enter data #10 or -1 to exit: 10
Enter data #11 or -1 to exit: 5
Enter data #12 or -1 to exit: 6
Enter data #13 or -1 to exit: 6
Enter data #14 or -1 to exit: 2
Enter data #15 or -1 to exit: 8
Enter data #16 or -1 to exit: 2
Enter data #17 or -1 to exit: 10
Enter data #18 or -1 to exit: -1

Original Data: 2 8 5 1 10 5 9 9 3 10 5 6 6 2 8 2 10
Final Data: 1 2 2 2 3 5 5 5 6 6 8 8 9 10 9 10 10

Example Execution #4:
Enter data #1 or -1 to exit: 7
Enter data #2 or -1 to exit: 7
Enter data #3 or -1 to exit: 7
Enter data #4 or -1 to exit: 7
Enter data #5 or -1 to exit: -1

Original Data: 7 7 7 7
Final Data: 7 7 7 7

Example Execution #5 (no -1 needed when 25 values [full set] are entered):
Enter data #1 or -1 to exit: 10
Enter data #2 or -1 to exit: 9
Enter data #3 or -1 to exit: 8
Enter data #4 or -1 to exit: 7
Enter data #5 or -1 to exit: 6
Enter data #6 or -1 to exit: 5
Enter data #7 or -1 to exit: 4
Enter data #8 or -1 to exit: 3
Enter data #9 or -1 to exit: 2
Enter data #10 or -1 to exit: 1
Enter data #11 or -1 to exit: 10
Enter data #12 or -1 to exit: 9
Enter data #13 or -1 to exit: 8
Enter data #14 or -1 to exit: 7
Enter data #15 or -1 to exit: 6
Enter data #16 or -1 to exit: 5
Enter data #17 or -1 to exit: 4
Enter data #18 or -1 to exit: 3
Enter data #19 or -1 to exit: 2
Enter data #20 or -1 to exit: 1
Enter data #21 or -1 to exit: 10
Enter data #22 or -1 to exit: 9
Enter data #23 or -1 to exit: 8
Enter data #24 or -1 to exit: 10
Enter data #25 or -1 to exit: 9

Original Data: 10 9 8 7 6 5 4 3 2 1 10 9 8 7 6 5 4 3 2 1 10 9 8 10 9
Final Data: 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 8 9 9 9 10 9 10 10 10

Example Execution #6:
Enter data #1 or -1 to exit: 10
Enter data #2 or -1 to exit: 9
Enter data #3 or -1 to exit: 8
Enter data #4 or -1 to exit: 7
Enter data #5 or -1 to exit: 6
Enter data #6 or -1 to exit: 5
Enter data #7 or -1 to exit: 4
Enter data #8 or -1 to exit: 3
Enter data #9 or -1 to exit: 2
Enter data #10 or -1 to exit: 1
Enter data #11 or -1 to exit: 10
Enter data #12 or -1 to exit: 9
Enter data #13 or -1 to exit: 8
Enter data #14 or -1 to exit: 7
Enter data #15 or -1 to exit: 6
Enter data #16 or -1 to exit: 5
Enter data #17 or -1 to exit: 4
Enter data #18 or -1 to exit: 3
Enter data #19 or -1 to exit: 2
Enter data #20 or -1 to exit: 1
Enter data #21 or -1 to exit: 10
Enter data #22 or -1 to exit: 9
Enter data #23 or -1 to exit: 8
Enter data #24 or -1 to exit: 10
Enter data #25 or -1 to exit: -1

Original Data: 10 9 8 7 6 5 4 3 2 1 10 9 8 7 6 5 4 3 2 1 10 9 8 10
Final Data: 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 8 9 9 10 9 10 10 10

Explanation / Answer

Looking at the data sets, here is the pseudo code: 1) Read data into array 2) Completely sort the array 3) Scan the array BACKWARDS until you find the first instance of the maximum value. 4) If this is not also the first entry in the sorted array, exchange it with the previous value (i.e. last instance of the next highest value). Now you have a "nearly sorted" array. As for coding it in C? Depends entirely on the level of C which you've reached. Presumably you know prompt the user for integers and store them in an array. Use qsort() to put the array in fully sorted order. Then, the final phase is something like: // N =number of entries in array int i, maxValue = array[N-1]; for (i = N-1; i > 0 && array[i] == maxValue; --i) ; // array[i] is last instance of penultimate value in sequence (or -1) if (i != -1) { array[i+1] = array[i]; array[i] =maxValue; }

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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