Problem
Make a quicksort program that can read from a text file called input.txt the values for the text file are provided below.
input.txt
3 5 16 12 1 4 7 9 10 200 100 4 6 17 13 2 8 15 11 21 199 105
Write QuickSort program that dynamically allocates an array (pointer-based array in heap memory area) large enough to hold numbers of test scores. After reading all the scores from the input.txt, store the data in a dynamic array structure and then display the data on the screen. You need to pass the input data to a function that sorts based on QuickSort them to display the ascending order and the descending order.
Again, the program should display the original list and the sorted list of scores. write read() to read the input.txt, save them into a pointer-based array (dynamic array) rather than general array notation [], and also use the pointer notation for QuickSort.
After reading the scores from Input.txt
Sample Output:
Display Input Data: 3 5 16 12 1 4 7 9 10 200 100.....
Ascending Order: 1 3 4 5 7 9 10 12 16 100 200.....
Descending Order: 200 100 16 12 10 9 7 5 4 3 1....
int partition( void *a, int low, int high )
{
int left, right;
void *pivot_item;
pivot_item = a[low];
pivot = left = low;
right = high;
while ( left < right ) {
/* Move left while item < pivot */
while( a[left] <= pivot_item ) left++;
/* Move right while item > pivot */
while( a[right] > pivot_item ) right--;
if ( left < right ) SWAP(a,left,right);
}
/* right is final position for the pivot */
a[low] = a[right];
a[right] = pivot_item;
return right;
}
As seen above, functions partition(int *input, int start, int end); and Quicksort(int *input, int start, int end); are the main bodies to complete the output.
A. Write Read() function to read the Input.txt and to store them into dynamically allocated array in heap memory. See the attached text file.
B. Use a pointer to point to each element in the dynamic array and to compare them to set the pivot.
C. Display the Input data, and display ascending order and descending order.