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 ...

2
Contributors
2
Replies
3
Views
11 Years
Discussion Span
Last Post by Rooro

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.

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;
}``````
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.