Random partitioning version of Quicksort

[Lelly]

Hello,
Can anybody explain to me how can I do:

Implement the Random partitioning version of Quicksort. Take care that your data array is not copied (by value) into your subroutines, because you will sort the RandomEnglishDictionary.txt file. Report the first, 1000th and last elements in your sorted list.

Thanks

[Momerath]

Quicksort - read the section on choice of pivot.

[Lelly]

thanks
I already read it
but my question how can I do my array without copy the data??
Also, what is this "Report the first, 1000th and last elements in your sorted list".

[mrnutty]

>>Implement the Random partitioning version of Quicksort

Means simply choose a random partition index from the array.

>>Take care that your data array is not copied (by value) into your subroutines

Means use reference, for example :

void quickSort(float array[] , const int size){
 //pick random pivot
 partition(array, pivot);
}
void partition(float subArray[], const int size){
}

in that case, the subArray will be the same as array and not a copy of it, since array are reference by default. If you have something like std::vector<int> then you need to pass it by reference explicitly.

void quickSort(std::vector<int>& array){
 //pick random pivot
 partition(array, pivot);
}
void partition(std::vector<int>& subArray[]){
}

notice the ampersand(i.e '&' ). That tells the compiler not to make a copy of the array and use the same array when passed into the function partition.

>>Report the first, 1000th and last elements in your sorted list.

It means, you need to sort the array, and print out the last 1000 items in the list.

[mike_2000_17]

>>>>Report the first, 1000th and last elements in your sorted list.

>>It means, you need to sort the array, and print out the last 1000 items in the list.

No, I think it means to print the first, 1000th and last elements. Say you have a std::vector named "my_sorted_array", once it has been sorted, you need to have a printout statement as so:

std::cout << my_sorted_array[0] << std::endl   //print the first element.
          << my_sorted_array[999] << std::endl //print the 1000th element.
          << my_sorted_array[my_sorted_array.size()-1] << std::endl; //print the last element.

That makes sense, the prof can check that you have a correctly sorted array if those three elements are the same as what he gets from his solution program. (you can also check if your algorithm is correct just by using a simpler, easier sort algorithm or by using std::sort).

[mrnutty]

>>>>Report the first, 1000th and last elements in your sorted list.

>>It means, you need to sort the array, and print out the last 1000 items in the list.

No, I think it means to print the first, 1000th and last elements. Say you have a std::vector named "my_sorted_array", once it has been sorted, you need to have a printout statement as so:

std::cout << my_sorted_array[0] << std::endl   //print the first element.
          << my_sorted_array[999] << std::endl //print the 1000th element.
          << my_sorted_array[my_sorted_array.size()-1] << std::endl; //print the last element.

That makes sense, the prof can check that you have a correctly sorted array if those three elements are the same as what he gets from his solution program. (you can also check if your algorithm is correct just by using a simpler, easier sort algorithm or by using std::sort).

Yes you are right.