Hello. i\'m supposed to making a C++ quicksort program to read names and years f

Question

Hello. i'm supposed to making a C++ quicksort program to read names and years from a file into an array and then sort them into alphabetical order. The full instructions are

"You are to write a program that does the following:

Read a list with names and year born from a file into an array.

There will not be more than 30 names in the file.

Write a function that will sort the names with the correct year born. (A dual sort)

You must use a recursive quicksort (a quick sort).

After sorting, print out the alphabetical list with the age.

The quicksort works as follows. Call quicksort with the the arrays and min and max. If min=max the list has just one element and is thus sorted.

Otherwise use the first element from min to max as a pivot value. Partition the list (from min to max) so that all of the values less than or equal to the pivot value are before it and all of the values greater than or equal to the pivot value are after it. The pivot value is now in its proper place. Call quicksort to sort the list from min to pivot-1 and call quicksort to sort the list from pivot+1 to max."

The sample file looks like this

"

I have no clue how to do this. Thank you in advance for your help!

Explanation / Answer

program :   

  #include <sstream>  #include <fstream>  #include <iostream>  #include <ctime>  using namespace std;          void quickSort(int *list, int start, int end)          {                  int pivot = (start + end)/2;                  int smallIndex = start;//lower sublist holds items >= pivot but           if ( start < end )                  {                          int tempA = list[start];                          list[start] = list[pivot];                          list[pivot] = tempA;                          for ( int i = start + 1; i <= end; i++ )                          {                                  if ( list[i] <= list[start] )                                  {                                          smallIndex+=1;                                          int tempB = list[i];                                          list[i] = list[smallIndex];                                          list[smallIndex] = tempB;                                  }                          }                          list[start] = list[smallIndex];                          list[smallIndex] = tempC;                          pivot = smallIndex;                          quickSort(list,start,pivot - 1);                          quickSort(list,pivot + 1,end);                  }          }  int main()  {          ifstream ifs;          ifs.open("reversedData1000000.txt");          int arraySize = 1000000;          int *list = new int[arraySize];          for ( int i = 0; i < arraySize; i++ )          {                  ifs >> list[i];          }          clock_t startTime = clock();          quickSort(list, 0, arraySize - 1);          clock_t endTime = clock();          clock_t duration = double(endTime - startTime);          string quickSortedList = printList(list,arraySize);          ifs.close();          ofs <<"Sort time: "<<duration<<" ms"<<endl<<endl<< quickSortedList;          ofs.close();          cout<<"Sort time:"<<duration<<" ms"<<endl;          return 0;  }  

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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