Quick sort and memory problems

E

Eva

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

David Hilsee

Eva said:
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.
 
J

John Harrison

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
 
I

Immanuel Albrecht

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
 
J

John Cochran

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

Eva

John Harrison said:
On 6 Aug 2004 14:27:27 -0700, Eva <[email protected]> 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
 
D

David Hilsee

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

John Cochran

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;
}
 
J

John Harrison

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
 
N

News For Mohan

Immanuel Albrecht said:
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
 
E

Eva

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


You are right, When I fixed it, the code works with no problems.
Thanks evebody for help.
Bee
 
J

Jerry Coffin

Immanuel Albrecht said:
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).

The depth of recursion with Quicksort is limited to Lg2(N) unless
you've competely screwed up its implementation. For 22000 items, that
comes to a worst case depth of 15. It may only reflect my own
ignorance, but I'm fairly sure I've never seen a reasonably conforming
implementation of C++ that targeted a machine that couldn't handle
calls 15 deep unless each call created a LOT of local variables.
 
R

Rich Grise

Sorry for going way OT like this, but this just got my nostalgia-bone
a-tinglin'. ;-) I once wrote a mailing list manager in MS DOS C. Their
list had about 8,000 entries. This was back when the biggest chunk
of memory there _was_ was 640K, and most of that was OS. :) And you
had to do some real gyrations to manage a piece of it bigger than
64K. 32K-1, if you wanted a reliable "file error" return.

I forget which method I used to sort it 32K at a time, but it came out
to 10 or 12 files - I just chopped it up, sorted each chunk, and then
merged them. I was pretty proud of myself.

Two years later I sold a copy of the list to the guy's competitor
for $800.00. >:-}

Cheers!
Rich
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,902
Latest member
Elena68X5

Latest Threads

Top