C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  quicksort query          C++Talk.NET Forum Index -> C++ language, library and standards View previous topic :: View next topic   Author Message Sambhaji Guest Posted: Fri Dec 15, 2006 6:55 am    Post subject: quicksort query Hi, I have a query regarding quick sort. I need to sort using quick sort. But quick sort has a problem sorting same numbers. i.e. it will not swap two numbers if they are same. This can be done easily using insertion sort. following the the example. assume we have an array of 5 intergers and each element is 0 index: 0 1 2 3 4 value: 0 0 0 0 0 after we do an insertion sort so that replacement will happen if value is less than or equal to other value then the result will be index: 4 3 2 1 0 value: 0 0 0 0 0 you can see that indexes have changed. Now when i try a quick sort, i get following output index: 0 1 2 3 4 value: 0 0 0 0 0 Quick sort does not swap numbers if they are same. Do you know any workaround so that quick sort will also give the same output as insertion sort. This is because I have a requirement in which I have to sort numbers using quick sort and if two numbers are same then they should appear in order of their index in the array from highest to lowest. Can you please help me. I will highly appreciate your help. Thanks, Sambhaji --- [ comp.std.c++ is moderated. To submit articles, try just posting with ] [ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ] [ --- Please see the FAQ before posting. --- ] [ FAQ: http://www.comeaucomputing.com/csc/faq.html ] Back to top Francis Glassborow Guest Posted: Fri Dec 15, 2006 4:35 pm    Post subject: Re: quicksort query In article <1166152153.511184.317120 (AT) 16g2000cwy (DOT) googlegroups.com>, Sambhaji <sambhaji.gayake (AT) gmail (DOT) com> writes Quote: Hi, I have a query regarding quick sort. I need to sort using quick sort. But quick sort has a problem sorting same numbers. i.e. it will not swap two numbers if they are same. This can be done easily using insertion sort. following the the example. Sorry, but I am having immense difficulty in grasping how you can tell if two identical things have, or have not been swapped. And why does it matter? If it does, they are not the same. Note that one feature of sort algorithms is exactly whether they do or do not preserve prior order. This is important where you are sorting objects on single attributes (for example, sorting people alphabetically by name and then chronologically by age. That is why C++ provides a stable_sort algorithm -- Francis Glassborow ACCU Author of 'You Can Do It!' and "You Can Program in C++" see http://www.spellen.org/youcandoit For project ideas and contributions: http://www.spellen.org/youcandoit/projects --- [ comp.std.c++ is moderated. To submit articles, try just posting with ] [ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ] [ --- Please see the FAQ before posting. --- ] [ FAQ: http://www.comeaucomputing.com/csc/faq.html ] Back to top Greg Herlihy Guest Posted: Fri Dec 15, 2006 5:01 pm    Post subject: Re: quicksort query Sambhaji wrote: Quote: I have a query regarding quick sort. I need to sort using quick sort. But quick sort has a problem sorting same numbers. i.e. it will not swap two numbers if they are same. This can be done easily using insertion sort. following the the example. A sorting algorithm that preserves the relative order of equally-ranked elements is called a "stable" sort. Your requirement is to perform a sort that will have exactly the opposite effect - in other words the relative order or any two equally-ranked elements has to be changed once the sorting has finished (I'm not sure there is a proper name for this kind of sorting algorithm). Quote: Can you please help me. I will highly appreciate your help. The obvious solution would be to reverse the order of the entire sequence of elements before applying a stable sorting algorithm (such as quicksort) to order them. Greg --- [ comp.std.c++ is moderated. To submit articles, try just posting with ] [ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ] [ --- Please see the FAQ before posting. --- ] [ FAQ: http://www.comeaucomputing.com/csc/faq.html ] Back to top Stephen Howe Guest Posted: Sun Dec 17, 2006 12:29 am    Post subject: Re: quicksort query 1st: This is the wrong newsgroup. It is for discussing the ISO C++ standard and related matters that pertain to the standardisation of C++ You most likely want comp.programming - to discuss algorithms comp.lang.c++ and/or comp.lang.c++.moderated - to discuss what C++ library facilities if you want to use to achieve this task. Followups set Quote: Quick sort does not swap numbers if they are same. Do you know any workaround so that quick sort will also give the same output as insertion sort. 2nd: This is incorrect. It just happens to be what you observe about your implementation or an implementation of these algorithms. What it seems to me that you are after is "stability" - that is equal values after being sorted appear in the same order they were in originally. stability is guaranteed by std::stable_sort(), std::list<T>.sort(), std::stable_partition(). Now it is a known fact that: quick sort for arrays is unstable insertion sort for arrays can be stable Quote: This is because I have a requirement in which I have to sort numbers using quick sort and if two numbers are same then they should appear in order of their index in the array from highest to lowest. 3rd: Then give an container v with random iterators, what you want is std::reverse(v.begin(), v.end()); std::stable_sort(v.begin(), v.end()); for equal elements to appear in reverse order or appearance. Stephen Howe --- [ comp.std.c++ is moderated. To submit articles, try just posting with ] [ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ] [ --- Please see the FAQ before posting. --- ] [ FAQ: http://www.comeaucomputing.com/csc/faq.html ] Back to top Graeme Prentice Guest Posted: Sun Dec 17, 2006 9:19 pm    Post subject: Re: quicksort query On Fri, 15 Dec 2006 11:01:20 CST, "Greg Herlihy" <greghe (AT) pacbell (DOT) net> wrote: Quote: The obvious solution would be to reverse the order of the entire sequence of elements before applying a stable sorting algorithm (such as quicksort) to order them. As you can see on Wikipedia, the fastest implementation of quicksort is an in place sort which is not stable and is most likely the sort provided by std::sort in most/all C++ libraries which the C++ standard specifies as having "approximately N log N comparisons on average" - which is the characteristic of quicksort. I believe it's possible to write a non in-place quicksort that is stable and also does "approximately N log N comparisons on average" as required by the standard. This would partition by forming a new list where elements greater than or equal to the pivot get added to the list starting at the top and growing down (reversing the original order) and elements less than the pivot get added to the new list from the bottom up (preserving original order). This uses more memory and probably does more move operations than the in place quicksort but the C++ standard doesn't give any guarantees on this criteria. The in-place quicksort is apparently often preferred (and is usually faster) to merge-sort even though merge sort has worst case N log N comparisons and less move operations because it requires only order log N extra memory so has better cache behaviour, and (according to Wikipedia), the comparison operations are all against the pivot instead of between two random elements. Hence merge sort (most likely C++ stable_sort) is probably a better choice than a stable quicksort. Graeme --- [ comp.std.c++ is moderated. To submit articles, try just posting with ] [ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ] [ --- Please see the FAQ before posting. --- ] [ FAQ: http://www.comeaucomputing.com/csc/faq.html ] Back to top ben.craig@gmail.com Guest Posted: Tue Dec 19, 2006 4:31 pm    Post subject: Re: quicksort query Quote: A sorting algorithm that preserves the relative order of equally-ranked elements is called a "stable" sort. One way to "stablize" a sort is to modify your comparison function slightly so that the initial ordering is taken into account. For example, instead of sorting a vector of values, one can instead sort a vector of (value, index) pairs, where the index is filled in before the sort starts. --- [ comp.std.c++ is moderated. To submit articles, try just posting with ] [ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ] [ --- Please see the FAQ before posting. --- ] [ FAQ: http://www.comeaucomputing.com/csc/faq.html ] Back to top Francis Glassborow Guest Posted: Sun Dec 24, 2006 11:43 pm    Post subject: Re: quicksort query In article <1166152153.511184.317120 (AT) 16g2000cwy (DOT) googlegroups.com>, Sambhaji <sambhaji.gayake (AT) gmail (DOT) com> writes Quote: Hi, I have a query regarding quick sort. I need to sort using quick sort. But quick sort has a problem sorting same numbers. i.e. it will not swap two numbers if they are same. This can be done easily using insertion sort. following the the example. I think this is the wrong place to ask such a question. It is about algorithms and not about either using C++ (still off topic here) or the C++ Standard. You also asked and were answered elsewhere (even though it was off-topic there as well). Your problem can also be easily address by reversing the order of your data and then using any stable sorting algorithm (and IIRC, Qicksort is NOT such an algorithm and so is of no use to you) -- Francis Glassborow ACCU Author of 'You Can Do It!' and "You Can Program in C++" see http://www.spellen.org/youcandoit For project ideas and contributions: http://www.spellen.org/youcandoit/projects --- [ comp.std.c++ is moderated. To submit articles, try just posting with ] [ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ] [ --- Please see the FAQ before posting. --- ] [ FAQ: http://www.comeaucomputing.com/csc/faq.html ] Back to top Colander Guest Posted: Thu Jan 11, 2007 6:52 pm    Post subject: Re: quicksort query Sambhaji wrote: Quote: Hi, I have a query regarding quick sort. I need to sort using quick sort. But quick sort has a problem sorting same numbers. i.e. it will not swap two numbers if they are same. This can be done easily using insertion sort. following the the example. assume we have an array of 5 intergers and each element is 0 index: 0 1 2 3 4 value: 0 0 0 0 0 after we do an insertion sort so that replacement will happen if value is less than or equal to other value then the result will be index: 4 3 2 1 0 value: 0 0 0 0 0 you can see that indexes have changed. Now when i try a quick sort, i get following output index: 0 1 2 3 4 value: 0 0 0 0 0 Quick sort does not swap numbers if they are same. Do you know any workaround so that quick sort will also give the same output as insertion sort. This is because I have a requirement in which I have to sort numbers using quick sort and if two numbers are same then they should appear in order of their index in the array from highest to lowest. Can you please help me. I will highly appreciate your help. Did you consider taking the index in account in your comparison function? --- [ comp.std.c++ is moderated. To submit articles, try just posting with ] [ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ] [ --- Please see the FAQ before posting. --- ] [ FAQ: http://www.comeaucomputing.com/csc/faq.html ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ language, library and standards All times are GMT Page 1 of 1   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.