Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement