#include <iostream> #include <fstream> using namespace std; void swap(int *a, int i, int j) { int t; if (i!=j) { t = a[i]; a[i] = a[j]; a[j] = t; } } int partition(int *arr, int left, int right) { int i, j; int pivot = (left + right) / 2; swap(arr, pivot, right); for (i=j=left; i<right; i++) { if (arr[i]<arr[right]) { swap(arr, i, j); j++; } } swap(arr,j,right); return j; } void quickSort(int *arr, int left, int right) { int pivot = partition(arr, left, right); if (left < pivot-1) quickSort(arr, left, pivot-1); if (pivot+1 < right) quickSort(arr, pivot+1, right); } int main() { int a[100], n, i; ifstream num_file; num_file.open("numbers.txt"); if (num_file.is_open()) { n=0; while (!num_file.eof()) num_file >> a[n++]; //n--; num_file.close(); cout << "Given array: "; for (i=0; i<n; i++) cout << a[i] << " "; quickSort(a, 0, n-1); cout << "\nSorted array: "; for (i=0; i<n; i++) cout << a[i] << " "; cout << endl; } else cout << "Error opening file!"; return 0; }
Friday, February 10, 2012
Quicksorting in C++
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment