Question

1) You must implement a recursive Quicksort algorithm that will read integers from the attached MyList.txt file. Your algorithm must sort the list(integers)in ascending order.

2)You must implement a recursive Mergesort algorithm that will read integers from the attached MyList.txt file. Your algorithm must sort the list(integers)in ascending order.

My List txt Values

7

3

4

1

4

4

9

9

4

8

4

5

3

9

2

3

7

0

6

4

4

5

0

1

9

2

1

7

4

7

8

7

8

3

6

3

5

9

7

3

7

8

8

2

5

9

1

2

7

2

0

1

7

5

4

3

05

9

2

0

7

8

9

8

4

8

2

9

2

2

1

1

5

7

5

7

5

8

7

3

2

7

8

0

1

5

1

7

6

9

2

9

6

3

9

2

6

0

5

8

9

7

5

3

5

4

2

4

5

7

7

6

9

7

1

9

4

2

9

1

1

6

4

6

5

7

3

5

1

6

8

5

9

3

5

Answer 1

//IF YOU ARE SATISFIED WITH THE CODE, KINDLY LEAVE A LIKE, ELSE COMMENT TO CLEAR DOUBTS

//I have used the same input in the MyList.txt file

//Quicksort.cpp

//C++ program for QuickSort

#include<iostream>

#include<fstream>

using namespace std;

void swap(int *a, int *b)

{

    int t = *a;

    *a = *b;

    *b = t;

}

int partition(int arr[], int low, int high)

{

    int pivot = arr[high]; // pivot

    int i = (low - 1);     // Index of smaller element

    for (int j = low; j <= high - 1; j++)

    {

        // If current element is smaller than or

        // equal to pivot

        if (arr[j] <= pivot)

        {

            i++; // increment index of smaller element

            swap(&arr[i], &arr[j]);

        }

    }

    swap(&arr[i + 1], &arr[high]);

    return (i + 1);

}

void quickSort(int arr[], int low, int high)

{

    if (low < high)

    {

        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);

        quickSort(arr, pi + 1, high);

    }

}

/* Function to print an array */

void printArray(int arr[], int size)

{

    int i;

    for (i = 0; i < size; i++)

        cout<< arr[i]<<"  ";

    cout<<"\n";

}

// Driver program to test above functions

int main()

{

    ifstream inFile;

    inFile.open("MyList.txt");

    int x;

    int size = 0;

    while(inFile>>x){

        size++;

    }

    int arr[size];

    inFile.close();

    inFile.open("MyList.txt");

    int i = 0;

    while(inFile>>x){

        arr[i++] = x;

    }

    quickSort(arr, 0, size - 1);

    cout<<"\n\nSorted array is\n";

    printArray(arr, size);

    return 0;

}

//Mergesort.cpp

// C++ program for Merge Sort

#include <iostream>

#include<fstream>

using namespace std;

void merge(int arr[], int l, int m, int r)

{

    int n1 = m - l + 1;

    int n2 = r - m;

    int L[n1], R[n2];

    // Copy data to temp arrays L[] and R[]

    for (int i = 0; i < n1; i++)

        L[i] = arr[l + i];

    for (int j = 0; j < n2; j++)

        R[j] = arr[m + 1 + j];

    int i = 0;

    int j = 0;

    int k = l;

    while (i < n1 && j < n2)

    {

        if (L[i] <= R[j])

        {

            arr[k] = L[i];

            i++;

        }

        else

        {

            arr[k] = R[j];

            j++;

        }

        k++;

    }

    while (i < n1)

    {

        arr[k] = L[i];

        i++;

        k++;

    }

    while (j < n2)

    {

        arr[k] = R[j];

        j++;

        k++;

    }

}

void mergeSort(int arr[], int l, int r)

{

    if (l < r)

    {

        int m = l + (r - l) / 2;

        mergeSort(arr, l, m);

        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);

    }

}

void printArray(int A[], int size)

{

    for (int i = 0; i < size; i++)

        cout << A[i] << "  ";

}

// Driver code

int main()

{

    ifstream inFile;

    inFile.open("MyList.txt");

    int x;

    int size = 0;

    while (inFile >> x)

    {

        size++;

    }

    int arr[size];

    inFile.close();

    inFile.open("MyList.txt");

    int i = 0;

    while (inFile >> x)

    {

        arr[i++] = x;

    }

    mergeSort(arr, 0, size - 1);

    cout << "\nSorted array is \n";

    printArray(arr, size);

    return 0;

}

CODE OUTPUT: