program1

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <iomanip>


const int MAX_WORDS = 100000;
const int MAX_WORD_LENGTH = 20;

//Prototypes
int strcasecmp(char *a, char *b);
void quicksort(std::string arr[], int left, int right);
void sort(std::string A[], int n);
void mergeSort(std::string A[], int left, int right, std::string temp[]);
void merge(std::string A[], int left, int leftEnd, int right, int rightEnd, std::string temp[]);

int main()
{
    std::string input_file_name, output_file_name;
    std::cout << "Welcome to the sorting words program." << "\n";
    std::cout << "Please enter the name of your input data file: ";
    std::cin >> input_file_name;
    std::cout << "Please enter the name of your output data file: ";
    std::cin >> output_file_name;

    std::ifstream input_file(input_file_name);
    if (!input_file)
    {
        std::cerr << "Error: Unable to open input file.\n";
        return 1;
    }

    std::string *words = new std::string[MAX_WORDS];
    std::string *words2 = new std::string[MAX_WORDS];
    int count = 0;
    std::string word;
    while (input_file >> word && count < MAX_WORDS)
    {
        words[count] = word;
        words2[count] = word;
        count++;
    }

    int N;
    std::cout << "\n" << count << " words were found in the file " << input_file_name << "\n";
    std::cout << "How many words per line should be printed? ";
    std::cin >> N;

    // Sort using Quicksort
    quicksort(words, 0, count - 1);
    // Sort using Mergesort
    sort(words2, count);

    std::ofstream output_file(output_file_name);
    if (!output_file)
    {
        std::cerr << "Error: Unable to open output file.\n";
        return 1;
    }
    output_file << count << " words sorted using quicksort" << "\n" << "\n";

    // Write sorted data to the output file for quicksort
    for (int i = 0; i < count; i += N)
    {
        for (int j = i; j < i + N && j < count; ++j)
        {
            output_file << std::setw(MAX_WORD_LENGTH) << std::left << words[j]; // Assuming each word has a maximum length of MAX_WORD_LENGTH characters
        }
        output_file << '\n';
    }

    output_file << "\n" << "\n" << count << " words sorted using merge sort, printed in reverse order" << "\n" << "\n";

    // Write sorted data to the output file for quicksort
    for (int i = 0; i < count; i += N)
    {
        for (int j = i; j < i + N && j <= count; ++j)
        {
            output_file << std::setw(MAX_WORD_LENGTH) << std::left << words2[count - (j-1)]; // Assuming each word has a maximum length of MAX_WORD_LENGTH characters
        }
        output_file << '\n';
    }


    std::cout << "End program.\n";

    return 0;
}

// -----------------------------------------
// ------------- Quick Sort ----------------
// -----------------------------------------

// Case-insensitive string comparison function
int strcasecmp(const char *a, const char *b)
{
    while (*a && *b)
    {
        int diff = tolower(*a) - tolower(*b);
        if (diff != 0)
        {
            return diff;
        }
        ++a;
        ++b;
    }
    return tolower(*a) - tolower(*b);
}

// Quicksort implementation
void quicksort(std::string arr[], int left, int right)
{
    if (left >= right)
        return;

    std::string pivot = arr[(left + right) / 2];

    int i = left, j = right;
    while (i <= j)
    {
        while (strcasecmp(arr[i].c_str(), pivot.c_str()) < 0)
        {
            ++i;
        }
        while (strcasecmp(arr[j].c_str(), pivot.c_str()) > 0)
        {
            --j;
        }
        if (i <= j)
        {
            std::swap(arr[i], arr[j]);
            ++i;
            --j;
        }
    }
    quicksort(arr, left, j);
    quicksort(arr, i, right);
}

// -----------------------------------------
// ------------- Merge sort ----------------
// -----------------------------------------

void sort(std::string A[], int n)
{
    std::string *temp = new std::string[n];
    mergeSort(A,0,n-1,temp);

    delete[] temp;
}

void mergeSort(std::string A[], int left, int right, std::string temp[])
{
    if (left < right)
    {
        int mid = (left+right)/2;
        mergeSort(A, left, mid, temp);
        mergeSort(A, mid+1, right, temp);
        merge(A, left, mid, mid+1, right, temp);
    }
}

void merge(std::string A[], int left, int leftEnd, int right, int rightEnd, std::string temp[])
{
    int saveStart = left;   // saves the starting index
    int index = left;       // to walkthrough temp

    while (left <= leftEnd && right <= rightEnd)
    {
        if (strcasecmp(A[left].c_str(), A[right].c_str()) < 0)
        {
            temp[index] = A[left];
            index++;
            left++;
        }
        else
        {
            temp[index] = A[right];
            index++;
            right++;
        }
    }

    while (left <= leftEnd)
    {
        temp[index] = A[left];
        index++;
        left++;
    }

    while (right <= rightEnd)
    {
        temp[index] = A[right];
        index++;
        right++;
    }

    for (int i = saveStart; i <= rightEnd; i++)
    {
        A[i] = temp[i];
    }
}