Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- //#include <bits/stdc++.h>
- using namespace std;
- void swap(int* a, int* b)
- {
- int t = *a;
- *a = *b;
- *b = t;
- }
- /* This function takes last element as pivot, places
- the pivot element at its correct position in sorted
- array, and places all smaller (smaller than pivot)
- to left of pivot and all greater elements to right
- of pivot */
- 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 the 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);
- }
- /* The main function that implements QuickSort
- arr[] --> Array to be sorted,
- low --> Starting index,
- high --> Ending index */
- void quickSort(int arr[], int low, int high)
- {
- if (low < high)
- {
- /* pi is partitioning index, arr[p] is now
- at right place */
- int pi = partition(arr, low, high);
- // Separately sort elements before
- // partition and after partition
- quickSort(arr, low, pi - 1);
- quickSort(arr, pi + 1, high);
- }
- }
- /* Function to print an array */
- void printArray(int arr[], int size)
- {
- ofstream data;
- data.open("sorted.txt");
- for (int i = 0; i < size; i++)
- {
- if (i % 100 == 0) data << endl;
- data << arr[i] << " ";
- }
- data << endl << endl;
- data << "Is viso surikiuota: " << size << " skaiciu." << endl;
- data.close();
- }
- int main()
- {
- ifstream input;
- input.open("output.txt");
- int arr[100000];
- int j = 0;
- while (input)
- {
- input >> arr[j];
- j++;
- }
- int n = sizeof(arr) / sizeof(arr[0]);
- quickSort(arr, 0, n - 1);
- cout << "Pavyko!" << endl;
- printArray(arr, n);
- input.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement