I have to write a quick sort code that Divide: pick a random element x (called p
ID: 3642529 • Letter: I
Question
I have to write a quick sort code thatDivide: pick a random element x (called pivot)
Using x, partition S (the list to sort) into:
L: elements less than x
E: elements equal x
G: elements greater than x
Recur: sort L and G
Conquer: join L, E and G
and i must read in a txt file where each number is separated by a space, and then sort these numbers. After the program sort the numbers i have to print them out in sorted order separated by spaces. I also have to use argc and argv to accept the filename.
Explanation / Answer
please rate - thanks
#include <iostream>
#include <fstream>
using namespace std;
void quicksort(int a[], int low, int high);
int split(int a[], int low, int high);
int main(int argc, char * argv[])
{
int a[20];
int low=0, high=0,i;
ifstream in;
ofstream out;
in.open(argv[1]);
if(in.fail())
{ cout<<"file did not open please check it ";
return 1;
}
in>>a[high];
while(in)
{high++;
in>>a[high];
}
cout<<"The unsorted array ";
for(i=0;i<high;i++)
cout<<a[i]<<" ";
cout<<endl;
low=0;
high--;
quicksort(a,low,high);
cout<<" The sorted array ";
for(i=0;i<=high;i++)
cout<<a[i]<<" ";
cout<<endl;
in.close();
return 0;
}
void quicksort(int a[], int low, int high)
{ int middle;
if(low >= high)
return;
middle = split(a, low, high);
quicksort(a, low, middle-1);
quicksort(a, middle+1, high);
}
int split(int a[], int low, int high)
{ int part_element = a[low];
for(; ;)
{
while(low < high && part_element <= a[high])
high--;
if(low >= high)
break;
a[low++] = a[high];
while(low < high && a[low] <= part_element)
low++;
if(low >= high)
break;
a[high--] = a[low];
}
a[high] = part_element;
return high;
}