Sambhaji wrote:

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

In article <1166152153.511184.317120@16g2000cwy.googlegroups.com>,
Sambhaji <sambhaji.gayake@gmail.com> writes
>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                      ]

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                      ]

In article <1166152153.511184.317120@16g2000cwy.googlegroups.com>,
Sambhaji <sambhaji.gayake@gmail.com> writes
>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                      ]

Sambhaji wrote:
>  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).

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

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

> 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

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

On Fri, 15 Dec 2006 11:01:20 CST, "Greg Herlihy" <greghe@pacbell.net>
wrote:

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

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