«

Hi,
I try to implement quick sort. I sort vectors by their first value.
10 2 3 4
9 3 5 6
10 4 5 6
must be
9 3 5 6
10 2 3 4
10 4 5 6
The prog works great on maybe 500 vectors, but I have an "Aborted(core
Dumped)" error message when try to sort 22000 of vectors. I thought
it's the memory problem. So after i get to arrays of vectors ( one is
less then pivot and other is bigger) and store the second array in the
file untill I'll be ready to work with it. It seems doesn't work.(
Same error message).
Do you have any suggestion,
Waiting for your reply,
Bee.

"Eva" <> wrote in message
news: om...
> Hi,
> I try to implement quick sort. I sort vectors by their first value.
> 10 2 3 4
> 9 3 5 6
> 10 4 5 6
> must be
> 9 3 5 6
> 10 2 3 4
> 10 4 5 6
> The prog works great on maybe 500 vectors, but I have an "Aborted(core
> Dumped)" error message when try to sort 22000 of vectors. I thought
> it's the memory problem. So after i get to arrays of vectors ( one is
> less then pivot and other is bigger) and store the second array in the
> file untill I'll be ready to work with it. It seems doesn't work.(
> Same error message).
> Do you have any suggestion,

Why aren't you using std::sort or std::stable_sort? Is this for homework?
How big are these vectors? Do they contain ints? I wouldn't suspect that
an allocation would fail, even for 22,000 vectors, unless they were pretty
big.

If you're really confused as to what your program is doing, you could always
use a debugger. However, is sounds like your program is simple enough that
other folks could help you with it if you gave a good description of it.

--
David Hilsee

On 6 Aug 2004 14:27:27 -0700, Eva <> wrote:

> Hi,
> I try to implement quick sort. I sort vectors by their first value.
> 10 2 3 4
> 9 3 5 6
> 10 4 5 6
> must be
> 9 3 5 6
> 10 2 3 4
> 10 4 5 6
> The prog works great on maybe 500 vectors, but I have an "Aborted(core
> Dumped)" error message when try to sort 22000 of vectors. I thought
> it's the memory problem. So after i get to arrays of vectors ( one is
> less then pivot and other is bigger) and store the second array in the
> file untill I'll be ready to work with it. It seems doesn't work.(
> Same error message).
> Do you have any suggestion,
> Waiting for your reply,
> Bee.

Yes post the code that doesn't work. Nobody here is psychic, we can't help
with code unless you post it.

john

(Eva) wrote:

> Hi, I try to implement quick sort. I sort vectors by their first
> value.
> The prog works great on maybe 500 vectors,
> but I have an "Aborted(core Dumped)" error message when try to sort
> 22000 of vectors. I thought it's the memory problem.

Ok, this is a wild guess, but: Are you using an recursive way of
implementing your quick-sort? If so, then you probably will mess up all
your programs stack and thus your program is killed by your OS.
So if you want to sort like 22000 vectors, you should not use the actual
stack, but rather use a stack class and turn your algorithm into a big
iteration loop (which can be tricky).

HTH

In article < >,
Eva <> wrote:
>Hi,
>I try to implement quick sort. I sort vectors by their first value.
>10 2 3 4
>9 3 5 6
>10 4 5 6
> must be
>9 3 5 6
>10 2 3 4
>10 4 5 6
>The prog works great on maybe 500 vectors, but I have an "Aborted(core
>Dumped)" error message when try to sort 22000 of vectors. I thought
>it's the memory problem. So after i get to arrays of vectors ( one is
>less then pivot and other is bigger) and store the second array in the
>file untill I'll be ready to work with it. It seems doesn't work.(
>Same error message).
>Do you have any suggestion,
>Waiting for your reply,
>Bee.

I assume that you're using the classic quicksort where you partition the
vector into two smallers lists and then recursively call the sort on the
two smaller lists. There are two common problems with quicksort routines.

1. Using the 1st or last element in the list tends to fail badly with
lists that are already in sorted or inverse sorted order. With either
of the above 2 cases quicksort degenerates into an O(N^2) algorithm.

2. Recursivily calling quicksort on *both* sublists. A much better method
is to recursivily call quicksort on the smaller of the two sublists and
sort the larger sublist using iteration. If you do this, then the worst
case stack depth is order log base 2 of N. If you recursivily call
quick sort for both sublists, then the worst case stack depth is order
N which for large lists will quickly blow out your stack.

"John Harrison" <> wrote in message news:<opsccjr6em212331@andronicus>...
> On 6 Aug 2004 14:27:27 -0700, Eva <> wrote:

>
> Yes post the code that doesn't work. Nobody here is psychic, we can't help
> with code unless you post it.
>
> john

HI again,
Thanks for respond,
Here is the code:

void vec_list_sort(list<vctr> VecList, int left, int right)
{
int l_hold, r_hold, i;
list<vctr>::iterator ptr_l, ptr_r;
vctr pivot;

l_hold=left;
r_hold=right;

ptr_l=VecList.begin();
for(i=0;i<left;i++)ptr_l++;

ptr_r=VecList.begin();
for(i=0;i<right;i++)ptr_r++;

pivot=(*ptr_l);
while(left<right){
while(((*ptr_r).at(4)>=pivot.at(4))&&(left<right)) {
right--;ptr_r--;
}
if(left!=right){
(*ptr_l)=(*ptr_r);
left++;
ptr_l++;
}
while(((*ptr_l).at(4)<=pivot.at(4))&&(left<right)) {
left++;ptr_l++;
}
if(left!=right){
(*ptr_r)=(*ptr_l);
right--;ptr_r--;
}
}
(*ptr_l)=pivot;
i=left;
left=l_hold;
right=r_hold;
if(left<i) vec_list_sort(VecList,left,i-1);
if(right>i)vec_list_sort(VecList,i+1,right);
}

The prog works fine for few cicles(sort function calls itself) untill
it starts to sort 2823-3052 vectors space. Prog stops with error
message Aborted (core dumped). Each vector is built of 6 integers
(some data for my thesis main prog) and I simply need to sort them by
vect.at(4). I used list, so I avoid the mess with arrays and
malloc().Any suggestions?
Bee

"Eva" <> wrote in message
news: om...
<snip>
> void vec_list_sort(list<vctr> VecList, int left, int right)
> {
> int l_hold, r_hold, i;
> list<vctr>::iterator ptr_l, ptr_r;
> vctr pivot;
>
> l_hold=left;
> r_hold=right;
>
> ptr_l=VecList.begin();
> for(i=0;i<left;i++)ptr_l++;
>
> ptr_r=VecList.begin();
> for(i=0;i<right;i++)ptr_r++;
>
> pivot=(*ptr_l);
> while(left<right){
> while(((*ptr_r).at(4)>=pivot.at(4))&&(left<right)) {
> right--;ptr_r--;
> }
> if(left!=right){
> (*ptr_l)=(*ptr_r);
> left++;
> ptr_l++;
> }
> while(((*ptr_l).at(4)<=pivot.at(4))&&(left<right)) {
> left++;ptr_l++;
> }
> if(left!=right){
> (*ptr_r)=(*ptr_l);
> right--;ptr_r--;
> }
> }
> (*ptr_l)=pivot;
> i=left;
> left=l_hold;
> right=r_hold;
> if(left<i) vec_list_sort(VecList,left,i-1);
> if(right>i)vec_list_sort(VecList,i+1,right);
> }
>
> The prog works fine for few cicles(sort function calls itself) untill
> it starts to sort 2823-3052 vectors space. Prog stops with error
> message Aborted (core dumped). Each vector is built of 6 integers
> (some data for my thesis main prog) and I simply need to sort them by
> vect.at(4). I used list, so I avoid the mess with arrays and
> malloc().Any suggestions?

I already asked this question, but I feel that I must ask this again: why
are you not using the functionality provided by the standard library? Is it
important that you write your own sorting function for your "thesis main
prog"? If you were willing to use std::vector<std::vector<int> > and
std::sort, this function would be very simple:

#include <vector>
#include <algorithm>

struct compare_vectors {
bool operator()( const std::vector<int>& a, const std::vector<int>& b )
const {
return a.at(4) < b.at(4);
}
};

void vec_list_sort( std::vector<std::vector<int> >& vecs ) {
std::sort( vecs.begin(), vecs.end(), compare_vectors() );
}

This may not be equivalent to what you have above because I didn't bother
trying to understand what you wrote. The code above sorts the
std::vector<int>s by their fifth element. Order of equivalent elements is
not preserved. Use std::stable_sort if that is desired.

--
David Hilsee

In article < >,
Eva <> wrote:
>"John Harrison" <> wrote in message news:<opsccjr6em212331@andronicus>...
>> On 6 Aug 2004 14:27:27 -0700, Eva <> wrote:
>
>>
>> Yes post the code that doesn't work. Nobody here is psychic, we can't help
>> with code unless you post it.
>>
>> john
>
>HI again,
>Thanks for respond,
>Here is the code:
SNIP YOUR CODE.

I would agree with Mr Harrison that if you can use the sort template then
do so. However if you have to implement a sort of a linked list yourself,
then using quicksort is not one of the better methods to use because of
its O(N^2) behavior when the list is already sorted or inverse sorted. Also
quicksort will have a stack size of O(N) if the input is near sorted or
inverse sorted. A much better method would be to use a merge sort. A merge
sort will always have O(N log N) behavior and the stack depth will be
O(log N) which will eliminate your problem with the stack blowing up.
A quick pseudo code for a merge sort follows:

LIST * sort(LIST * input)
{
LIST * list1;
LIST * list2;
LIST * tail;
LIST * head;

// If input list is empty or has only 1 node, return it */
if (input == NULL || input->next == NULL) return input;

// Only lists of length 2 or greater will reach this point.

// Split input list into 2 approximately equal sized lists.
// Method used here is to have 2 pointers, a fast pointer and a slow
// pointer where the fast pointer moves twice as fast as the slow
// pointer. When the fast pointer reaches the end of the list, the
// slow pointer will be pointing to the last node of one of the desired
// half lists.
list1 = input;
list2 = input;
tail = input;
for(; {
tail = tail->next;
if (tail == NULL) break;
tail = tail->next;
if (tail == NULL) break;
list2 = list2->next;
}
tail = list2; // Split input list into 2 smaller lists
list2 = tail->next;
tail->next = NULL;

// Now recursively sort the 2 smaller lists.
list1 = sort(list1);
list2 = sort(list2);

// Now merge the 2 lists together
// Note: Both list1 and list2 will be non-empty because of
// the IF statement at the beginning of the function.
if (compare(*list1, *list2) < 0) {
head = list1;
tail = list1;
list1 = list1->next;
} else {
head = list2;
tail = list2;
list2 = list2->next;
}

// Continue to merge nodes as long as both lists are not empty.
while(list1 != NULL && list2 != NULL) {
if (compare(*list1, *list2) < 0) {
tail->next = list1;
tail = list1;
list1 = list1->next;
} else {
tail->next = list2;
tail = list2;
list2 = list2->next;
}
}

// At this point there will be exactly 1 empty list and 1 non-empty list.
// Link the non-empty list to the end of the list being built.
if (list1 != NULL) {
tail->next = list1;
} else {
tail->next = list2;
}

return head;
}

On 8 Aug 2004 17:09:20 -0700, Eva <> wrote:

> "John Harrison" <> wrote in message
> news:<opsccjr6em212331@andronicus>...
>> On 6 Aug 2004 14:27:27 -0700, Eva <> wrote:
>
>>
>> Yes post the code that doesn't work. Nobody here is psychic, we can't
>> help
>> with code unless you post it.
>>
>> john
>
> HI again,
> Thanks for respond,
> Here is the code:
>
> void vec_list_sort(list<vctr> VecList, int left, int right)
> {

Is this the real code? It has the obvious problem that it only sorts a
copy of the list not the original list. I think you meant

void vec_list_sort(list<vctr>& VecList, int left, int right)
{

With this change I was able to sort lists of 3000 and 4000 elements (of
random numbers) without problems. And I can't see any obvious bugs. Maybe
your real bug is elsewhere in your code.

But your code is very inefficient. And I have to wonder why you've gone to
all this trouble when the standard C++ library already has routines for
sorting lists. And since you are sorting I also wonder why you are using a
list not a vector. Sorting vectors is inherently more efficient than
sorting lists and the standard library has routines for sorting vectors
too.

As an experiment, if nothing else, why not use the standard library list
sorting routine. If you are still getting a crash that would indicate a
bug elsewhere in your code. If you need help doing this then post again.

john

"Immanuel Albrecht" <> wrote in message
news:cf5vmn$8re$05$...
> (Eva) wrote:
>
> > Hi, I try to implement quick sort. I sort vectors by their first
> > value.
> > The prog works great on maybe 500 vectors,
> > but I have an "Aborted(core Dumped)" error message when try to sort
> > 22000 of vectors. I thought it's the memory problem.
>
> Ok, this is a wild guess, but: Are you using an recursive way of
> implementing your quick-sort? If so, then you probably will mess up all
> your programs stack and thus your program is killed by your OS.
> So if you want to sort like 22000 vectors, you should not use the actual
> stack, but rather use a stack class and turn your algorithm into a big
> iteration loop (which can be tricky).
>
> HTH