Quick-Sort using multi-threading USING C++ The program gets a list of integer va

Question

Quick-Sort using multi-threading USING C++

The program gets a list of integer values specified in an input file named input.txt. Using the recursive threading and quick sort technique, the program should sort the input list. The input “input.txt” consists of several text based lines. The first line indicates size for the list of numbers to be sorted (n). The next “n” lines contain the input numbers. The output (“output.txt”) should be the sorted list, each number in a line. To follow the recursive threading method in the quick sort your implementation should meet the following requirements:

- The main function should read input file and fill an integer array. Then it runs “QuickSort” function as a new thread and passes the input array to that thread. Main function should wait until QuickSort algorithm is finished and then print out the sorted array in the output.

- The “QuickSort” function is responsible to select a “pivot” and divide its input array (e.g. arr) to two sub-arrays (e.g. leftArr and rightArr) as defined in quicksort algorithm. It then calls the QuickSort recursively in a new thread for leftArr and/or rightArr as needed. The main requirement of this assignment is that the implementation should enable leftArr and rightArr be sorted concurrently in two different threads.

Input.txt

8

3304

8221

26849

14038

1509

6367

7856

21362

Output.txt

1509

3304

6367

7856

8221

14038

21362

26849

Explanation / Answer

#include <iostream>
#include <cstdlib>
#include <pthread.h>
using namespace std;

struct vect{
   public:
       int* array;
       int low;
       int high;
       vect(int* l,int lw,int hgh){
           array = l;
           low = lw;
           high = hgh;
       }
};

int partition(int* l,int low,int high){
   int pivot = l[high];
   int index = low;
   for (int j = low+1; j < high; j++){
       if (l[j] <= pivot){
           int temp = l[index];
           l[index] = l[j];
           l[j] = temp;
           index++;
       }
   }
   int temp = l[index];
   l[index] = pivot;
   l[high] = temp;
   return index;
}

void quick_sort(vect* v){
   int* l = v->array;
   int low = v->low;
   int high = v->high;
   if (high > low){
       int pos = partition(l,low,high);
       pthread_t temp_1;
       vect* v_1 = new vect(l,low,pos-1);
       int rc = pthread_create(&temp_1, NULL, quick_sort,&v_1);
       pthread_exit(NULL);
       pthread_t temp_2;
       vect* v_2 = new vect(l,pos+1,high);
       rc = pthread_create(&temp_2, NULL, quick_sort,&v_2);
       pthread_exit(NULL);
   }

}

int main(){
   int* l = new int[1000];
   int n = 0;
   ifstream infile;
   infile.open("input.txt");
   while (!infile.eof()){
       infile >> l[n];
       n += 1;
   }
   infile.close();
   vect* v = new vect(l,0,n-1);
   quick_sort(v);

   ofstream outfile;
   outfile.open("output.txt");
   for (int i = 0; i < n; i++){
       outfile << v->l[i] << endl;
   }
   outfile.close();
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

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