Quick sort and memory problems

Discussion in 'C++' started by Eva, Aug 6, 2004.

  1. Eva

    Eva Guest

    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, Aug 6, 2004
    #1
    1. Advertising

  2. Eva

    David Hilsee Guest

    "Eva" <> wrote in message
    news:...
    > 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
     
    David Hilsee, Aug 6, 2004
    #2
    1. Advertising

  3. 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
     
    John Harrison, Aug 7, 2004
    #3
  4. (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
     
    Immanuel Albrecht, Aug 8, 2004
    #4
  5. Eva

    John Cochran Guest

    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 Cochran, Aug 8, 2004
    #5
  6. Eva

    Eva Guest

    "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, Aug 9, 2004
    #6
  7. Eva

    David Hilsee Guest

    "Eva" <> wrote in message
    news:...
    <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
     
    David Hilsee, Aug 9, 2004
    #7
  8. Eva

    John Cochran Guest

    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;
    }
     
    John Cochran, Aug 9, 2004
    #8
  9. 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
     
    John Harrison, Aug 9, 2004
    #9
  10. "Immanuel Albrecht" <> wrote in message
    news:cf5vmn$8re$05$-online.com...
    > (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
     
    News For Mohan, Aug 10, 2004
    #10
  11. Eva

    Eva Guest

    >
    > 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
     
    Eva, Aug 13, 2004
    #11
  12. Eva

    Jerry Coffin Guest

    Immanuel Albrecht <> wrote in message news:<cf5vmn$8re$05$-online.com>...
    > (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).


    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.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
     
    Jerry Coffin, Aug 13, 2004
    #12
  13. Eva

    Rich Grise Guest

    News For Mohan wrote:

    >
    > "Immanuel Albrecht" <> wrote in message
    > news:cf5vmn$8re$05$-online.com...
    >> (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


    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
     
    Rich Grise, Aug 23, 2004
    #13
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. JKop
    Replies:
    11
    Views:
    934
  2. John
    Replies:
    1
    Views:
    343
    Ivan Vecerina
    Apr 16, 2005
  3. Replies:
    13
    Views:
    748
  4. Brent White
    Replies:
    2
    Views:
    553
    Peter Bromberg [C# MVP]
    Jan 30, 2008
  5. Navin
    Replies:
    1
    Views:
    761
    Ken Schaefer
    Sep 9, 2003
Loading...

Share This Page