A few concetps about sorting algorithms and questions
A sorting algorithm is stable if whenever there are two
records R and S with the same key and with R appearing
before S in the original list, R will appear before
S in the sorted list. For example:
(1, 2), (1, 4) --> sorting algo which gives
(1, 2) (1, 4) is stale;
(1, 2), (1, 4) --> sorting algo which gives
(1, 4) (1, 2) is not stale.
A sorting algorithm is in place if only O(1) extra memory is
needed beyond the items being sorted. Comments: when define
the term in place, a book I read said
only O(1) or O(lgn) extra memory is needed.
Let us stick with the first definition: only O(1) memory is allowed
for in place algorithm.
Under these classifications and standard implementations (e.g.,
a not standard implementation of bubble sort can use as such
memory as the coder wants):
bubble, insertion, and merge are stable;
heap and quick are unstable.
bubble, insertion and heap are in place;
merge is not in place.
Q1: Is quick sort considered to be in place? Assume that we use O(lgn)
stack length for quicksort, such as the following implementation:
void quicksort(int* a, int p, int r)
{
while(p<r)
{
int q = partition(a, p, r);
// only sort the smaller part
if(q-p<r-q)
{
quicksort(a, p, q-1);
}
else
{
quicksort(a, q+1, r);
}
}
}
Q2: Is there a stable and in place sorting algorithm (based
on comparsion)?
[此贴子已经被作者于2007-9-22 20:25:29编辑过]
