question about sorting

[Rooro]

Hello everyone ... : )

i'm studying data structure and i'm trying to collect all the point in this course . what I have now is a question about sorting . I want to learn how can I do it and code it in the right way ..

The median of set with an old number of elements is the middle value if data items are arranged in order. An efficient algorithm to find the median that does not require first ordering the entire set can be obtained by modifying the quick sort algorithm. We use function split() to position a pivot element .If this pivot is positioned at location (n+1)/2,it is the median : otherwise, one of the two sublists produced by split() contains the median , and that sublist can be processed recursively. Write a function to fine the median of a list using this method.

Thanks ...

[Narue]

We're not going to do it for you. Please try it yourself and see what you can come up with. You'll learn more that way. Also, the algorithm is called QuickSelect, if you want to do some research on it.

[Rooro]

thanks Narue : )

---------

This is the code for split() , can you help me to understand what can I do, to solve the question ?

template <typename ElementType> 
void split (ElementType x[ ], int first, int last, int & pos)
 { 
ElementType pivot = x[first]; // pivot element
 int left = first, // index for left search 
right = last; // index for right search
 while (left < right) {  while (pivot < x) // Search from right for element <= pivot  
   right--; 
  // Search from left for element > pivot 
  while (left < right && (x < pivot || x == pivot)) 
     left++;
   if (left < right) // If searches haven't met
   swap (x[left, x); // interchange elements 
    } // End of searches; place pivot in correct position 
 pos = right; 
            x[first] = x[pos]; 
            x[pos] = pivot; 
}