14 Replies - 1570 Views - Last Post: 21 February 2011 - 02:42 PM Rate Topic: -----

#1 ipushmycar  Icon User is offline

  • D.I.C Regular

Reputation: 86
  • View blog
  • Posts: 390
  • Joined: 29-August 10

Sorting a vector of objects by their attributes with quick sort.

Posted 20 February 2011 - 02:19 PM

Hey guys I am trying to sort a vector of "Movies". Movies is a class I made with attributes but I only want to sort them by either their title which is a string or by their year, an int. I was able to get selection sort and merge sort to sort them just not quick sort. When I run my program it comes up with subscript out of range. My quicksortYear works fine though. Any ideas why it has trouble with title?

Thanks,
Ipush

Driver where it is called:
    

//Quick Sort
    cout << "Sorting movies by Title with Quick Sort." << endl;
    cout << endl;

    quickSort(movies);
    
    cout << "After sort:" << endl;
    displayTitle(movies);


Quick sort:
#include <iostream>
#include <string>
#include "utilities.h"
#include "Movie.h"
#include "quickSort.h"
using namespace std;


void quickSort(vector<Movie> &a)
{
//------------------------------------------------------
// driver subprogram to sort an entire vector into
// ascending order with quickSort.
//------------------------------------------------------
    quickSort(a, 0, a.size()-1);
}

//----------------------------------------------------------------------------
//
    void quickSort(vector<Movie> &a, int left, int right)
    {
    //------------------------------------------------------
    // quickSort(): a recursive partitioning-based sort
    //------------------------------------------------------

        if (left < right)
        {
             int k = partition(a, left, right);
            quickSort(a, left, k);
            quickSort(a, k+1, right);
        }
    }

//----------------------------------------------------------------------------
//
    int partition(vector<Movie> &a, int left, int right)
    {
    //------------------------------------------------------
    // partition(): rearrange a into 3 sublists:
    // - a sublist a[left] ... a[j-1] of values at most a[j]
    // - a sublist a[j], and 
    // - a sublist a[j+1] ... a[right] of values at least a[j]
    //------------------------------------------------------
        string pivot = a[left].getTitle();
        int i = left - 1;
        int j = right + 1;
        do {
            do
            { 
                j-- ; 
            } while (a[j].getTitle().compare(pivot) != -1) ;
            
            do
            { 
                i++ ; 
            } while (a[i].getTitle().compare(pivot) != 1);
            
            if (i < j)
                exchange(a[i], a[j]);
                
        } while (i < j);
        
        return j;
    }



int partitionYear(vector<Movie> &a, int left, int right)
{
//------------------------------------------------------
// partition(): rearrange a into 3 sublists:
// - a sublist a[left] ... a[j-1] of values at most a[j]
// - a sublist a[j], and 
// - a sublist a[j+1] ... a[right] of values at least a[j]
//------------------------------------------------------
    int pivot = a[left].getYear();
    int i = left - 1;
    int j = right + 1;
    do {
        do
        { 
            j-- ; 
        } while (a[j].getYear() > pivot);
        
        do
        { 
            i++ ; 
        } while (a[i].getYear() < pivot);
        
        if (i < j)
            exchange(a[i], a[j]);
            
    } while (i < j);
    
    return j;
}
void quickSortYear(vector<Movie> &a)
{
//------------------------------------------------------
// driver subprogram to sort an entire vector into
// ascending order with quickSort.
//------------------------------------------------------
    quickSortYear(a, 0, a.size()-1);
}

//----------------------------------------------------------------------------
//
void quickSortYear(vector<Movie> &a, int left, int right)
{
//------------------------------------------------------
// quickSort(): a recursive partitioning-based sort
//------------------------------------------------------

    if (left < right)
    {
        int k = partitionYear(a, left, right);
        quickSortYear(a, left, k);
        quickSortYear(a, k+1, right);
    }
}


This post has been edited by ipushmycar: 20 February 2011 - 02:27 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Sorting a vector of objects by their attributes with quick sort.

#2 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Sorting a vector of objects by their attributes with quick sort.

Posted 20 February 2011 - 02:27 PM

Here's one:
do
            { 
                i++ ; 
            } while (a[j].getTitle().compare(pivot) != 1);



If that doesn't solve your problem, don't you think you should learn to find your own logical errors, not ask us to do it for you? Just saying ...

Either trace it with a debugger, or put in some intelligent print statements at various points in the program so you can see what's going wrong.
Was This Post Helpful? -1
  • +
  • -

#3 Salem_c  Icon User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 1579
  • View blog
  • Posts: 3,007
  • Joined: 30-May 10

Re: Sorting a vector of objects by their attributes with quick sort.

Posted 20 February 2011 - 02:33 PM

Is writing your own code part of the exercise?

Or can you use the build-in sort functionality
http://www.cplusplus...algorithm/sort/
Was This Post Helpful? 0
  • +
  • -

#4 ipushmycar  Icon User is offline

  • D.I.C Regular

Reputation: 86
  • View blog
  • Posts: 390
  • Joined: 29-August 10

Re: Sorting a vector of objects by their attributes with quick sort.

Posted 20 February 2011 - 06:19 PM

View Postr.stiltskin, on 20 February 2011 - 02:27 PM, said:

Here's one:
do
            { 
                i++ ; 
            } while (a[j].getTitle().compare(pivot) != 1);



If that doesn't solve your problem, don't you think you should learn to find your own logical errors, not ask us to do it for you? Just saying ...

Either trace it with a debugger, or put in some intelligent print statements at various points in the program so you can see what's going wrong.


That did not make a difference. I also do not believe that is even a logic error since it returns 1 if it is order -1 if it is not... just saying.

View PostSalem_c, on 20 February 2011 - 02:33 PM, said:

Is writing your own code part of the exercise?

Or can you use the build-in sort functionality
http://www.cplusplus...algorithm/sort/



Part of the exercise to use the sorting algorithms.

This post has been edited by ipushmycar: 20 February 2011 - 06:53 PM

Was This Post Helpful? -1
  • +
  • -

#5 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Sorting a vector of objects by their attributes with quick sort.

Posted 20 February 2011 - 07:31 PM

View Postipushmycar, on 20 February 2011 - 08:19 PM, said:

That did not make a difference. I also do not believe that is even a logic error since it returns 1 if it is order -1 if it is not... just saying.

Well, that's a rather arrogant reply. Of course it makes a difference, since it was obviously an error -- it makes no sense to be incrementing i and then testing a[j]. It's not the only error -- but that doesn't mean it didn't have to be corrected.

Of course there's a logic error -- by definition, since the function is not giving the correct results.

In fact, there are two factors that you are not handling correctly:
1. you are testing for values that are greater than the pivot and for values that are less than the pivot. What about when a value is found that is EQUAL to the pivot?

2. You are arbitrarily using the leftmost element as the pivot, which is fine. What isn't fine is that you never move the pivot from that position, so how is the array ever going to be sorted?
Was This Post Helpful? 1
  • +
  • -

#6 ipushmycar  Icon User is offline

  • D.I.C Regular

Reputation: 86
  • View blog
  • Posts: 390
  • Joined: 29-August 10

Re: Sorting a vector of objects by their attributes with quick sort.

Posted 21 February 2011 - 06:21 AM

View Postr.stiltskin, on 20 February 2011 - 07:31 PM, said:

View Postipushmycar, on 20 February 2011 - 08:19 PM, said:

That did not make a difference. I also do not believe that is even a logic error since it returns 1 if it is order -1 if it is not... just saying.

Well, that's a rather arrogant reply. Of course it makes a difference, since it was obviously an error -- it makes no sense to be incrementing i and then testing a[j]. It's not the only error -- but that doesn't mean it didn't have to be corrected.

Of course there's a logic error -- by definition, since the function is not giving the correct results.

In fact, there are two factors that you are not handling correctly:
1. you are testing for values that are greater than the pivot and for values that are less than the pivot. What about when a value is found that is EQUAL to the pivot?

2. You are arbitrarily using the leftmost element as the pivot, which is fine. What isn't fine is that you never move the pivot from that position, so how is the array ever going to be sorted?


I am not incrementing i and using a[j]? I am getting a vector subscript out of bounds error like stated above so wouldn't that be syntax?

1) Yes, your right I need to do something about when they are equal but still that shouldn't be giving me that an out of bounds or vector subscript error.

2) Yes, I am exchanging them.

            if (i < j)
                exchange(a[i], a[j]);


I feel as if you did not read the question or look at the code very carefully...
Was This Post Helpful? 0
  • +
  • -

#7 jimblumberg  Icon User is offline

  • member icon


Reputation: 3846
  • View blog
  • Posts: 11,771
  • Joined: 25-December 09

Re: Sorting a vector of objects by their attributes with quick sort.

Posted 21 February 2011 - 07:48 AM

Have you run this code through your debugger?

If not why not?

The debugger should tell you where the error is occurring and you should be able to look at the values of the variables at the time of the crash. And you can step through the code line by line inspecting the variables and logic.

With the partial code you supplied it is very difficult to find your problem, a complete compilable program would probably help us to help you, but the debugger the best choice.


Jim
Was This Post Helpful? 1
  • +
  • -

#8 ipushmycar  Icon User is offline

  • D.I.C Regular

Reputation: 86
  • View blog
  • Posts: 390
  • Joined: 29-August 10

Re: Sorting a vector of objects by their attributes with quick sort.

Posted 21 February 2011 - 08:32 AM

View Postjimblumberg, on 21 February 2011 - 07:48 AM, said:

Have you run this code through your debugger?

If not why not?

The debugger should tell you where the error is occurring and you should be able to look at the values of the variables at the time of the crash. And you can step through the code line by line inspecting the variables and logic.

With the partial code you supplied it is very difficult to find your problem, a complete compilable program would probably help us to help you, but the debugger the best choice.


Jim



I have used the debugger at both of the while loops where I test the title vs the pivot but they always go out of bounds which makes sense, and at the outer while, which also seems to work. So as of now I do not understand why it goes out of bounds. I'll keep trying at different spots, I am also using cout like r.stiltskin suggested but its had to determine where it stops when the program crashes.
Was This Post Helpful? 0
  • +
  • -

#9 jimblumberg  Icon User is offline

  • member icon


Reputation: 3846
  • View blog
  • Posts: 11,771
  • Joined: 25-December 09

Re: Sorting a vector of objects by their attributes with quick sort.

Posted 21 February 2011 - 08:40 AM

Quote

I have used the debugger at both of the while loops where I test the title vs the pivot but they always go out of bounds which makes sense, and at the outer while, which also seems to work.


What do you mean by "go out of bounds"?

When I think of out of bounds I think that you are using an array subscript that is larger than the array size.


Jim
Was This Post Helpful? 0
  • +
  • -

#10 ipushmycar  Icon User is offline

  • D.I.C Regular

Reputation: 86
  • View blog
  • Posts: 390
  • Joined: 29-August 10

Re: Sorting a vector of objects by their attributes with quick sort.

Posted 21 February 2011 - 09:16 AM

View Postjimblumberg, on 21 February 2011 - 08:40 AM, said:

Quote

I have used the debugger at both of the while loops where I test the title vs the pivot but they always go out of bounds which makes sense, and at the outer while, which also seems to work.


What do you mean by "go out of bounds"?

When I think of out of bounds I think that you are using an array subscript that is larger than the array size.


Jim


Yes, it says that my vector goes out of bounds.
Was This Post Helpful? 0
  • +
  • -

#11 jimblumberg  Icon User is offline

  • member icon


Reputation: 3846
  • View blog
  • Posts: 11,771
  • Joined: 25-December 09

Re: Sorting a vector of objects by their attributes with quick sort.

Posted 21 February 2011 - 09:34 AM

Quote

Yes, it says that my vector goes out of bounds.


So why worry about where it crashes? Your problem is that you are trying to access a vector element that does not exist. This is your problem. You now know where your problem is located, now you need to determine why. You need to examine the variables that you are using for your vector indexes and determine why your logic is flawed.


Jim
Was This Post Helpful? 0
  • +
  • -

#12 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Sorting a vector of objects by their attributes with quick sort.

Posted 21 February 2011 - 09:37 AM

Very often, assignments are posted here in which the students are asked to specify pre- and postconditions for their functions. And more often than not, those pre- and postconditions are so trivial and obvious that they aren't worth the time it takes to write them.

Quicksort's partition function, on the other hand, is a different matter. It's precondition isn't particularly enlightening, but the postcondition is. If you can state clearly the intended postcondition of partition I think it will help you to focus on how to correct it. Are you familiar with the concept of "postcondition"?

Another suggestion: first write a quicksort that sorts ints. It will be less confusing and easier to test. Once you have that working correctly it will be a simple task to modify it to handle your Movies or any other data type.

Finally, try visually tracing what it's doing. Write an array of ints on paper, point to "left" with your left index finger, point to "right" with your right, and try executing your program with your fingers to see if it's doing what you intended in order to achieve your stated postcondition.
Was This Post Helpful? 0
  • +
  • -

#13 ipushmycar  Icon User is offline

  • D.I.C Regular

Reputation: 86
  • View blog
  • Posts: 390
  • Joined: 29-August 10

Re: Sorting a vector of objects by their attributes with quick sort.

Posted 21 February 2011 - 10:02 AM

View Postr.stiltskin, on 21 February 2011 - 09:37 AM, said:

Very often, assignments are posted here in which the students are asked to specify pre- and postconditions for their functions. And more often than not, those pre- and postconditions are so trivial and obvious that they aren't worth the time it takes to write them.

Quicksort's partition function, on the other hand, is a different matter. It's precondition isn't particularly enlightening, but the postcondition is. If you can state clearly the intended postcondition of partition I think it will help you to focus on how to correct it. Are you familiar with the concept of "postcondition"?

Another suggestion: first write a quicksort that sorts ints. It will be less confusing and easier to test. Once you have that working correctly it will be a simple task to modify it to handle your Movies or any other data type.

Finally, try visually tracing what it's doing. Write an array of ints on paper, point to "left" with your left index finger, point to "right" with your right, and try executing your program with your fingers to see if it's doing what you intended in order to achieve your stated postcondition.



Sadly, I have been trying to do it for a while. Here is what I have gotten:

4 Movies:
The longest yard
the hangover
role models
the 40 year old
dodgeball

pivot: The longest Yard
left = 0,
right = 4
i = -1,0
j = 5,4

exchange but it crashes before here with j, I don't know why.


EDIT: I have quick sort written in java, c++ and they both work with any type of numbers just not strings. I was able to get my quicksortYear to work with the object.getYear() but not with strings. Am i determining if they are in alphabetical order correctly? Every time I tested .compare it would return -1 if it was in order 1 if not. I did not test it with everything but my current 5 movies and other words.

This post has been edited by ipushmycar: 21 February 2011 - 10:04 AM

Was This Post Helpful? 0
  • +
  • -

#14 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Sorting a vector of objects by their attributes with quick sort.

Posted 21 February 2011 - 11:53 AM

Look at this line: while(a[j].getTitle().compare(pivot) != -1)
Suppose pivot is the "lowest" string in the vector, meaning that every string in the vector (including pivot itself) is >= pivot. So when will your program stop decrementing j? When it crashes.

The same problem applies to the code that increments i.

Fix that and it should solve the segfault problem (but you still have logical errors in the program).

edit: You shouldn't really be using 1 and -1 explicitly in these expressions because the standard only says that compare will return a positive or negative number, or 0. Use 0 in your test expressions: i.e. >0, >=0, <0, <=0 or ==0.

This post has been edited by r.stiltskin: 21 February 2011 - 01:07 PM

Was This Post Helpful? 1
  • +
  • -

#15 ipushmycar  Icon User is offline

  • D.I.C Regular

Reputation: 86
  • View blog
  • Posts: 390
  • Joined: 29-August 10

Re: Sorting a vector of objects by their attributes with quick sort.

Posted 21 February 2011 - 02:42 PM

Working code if anyone was interested. Thanks for the help.

#include <iostream>
#include <string>
#include "utilities.h"
#include "Movie.h"
#include "quickSort.h"
using namespace std;


void quickSort(vector<Movie> &a)
{
//------------------------------------------------------
// driver subprogram to sort an entire vector into
// ascending order with quickSort.
//------------------------------------------------------
    quickSort(a, 0, a.size()-1);
}

//----------------------------------------------------------------------------
//
void quickSort(vector<Movie> &a, int left, int right)
{
//------------------------------------------------------
// quickSort(): a recursive partitioning-based sort
//------------------------------------------------------

    if (left < right)
    {
        int k = partition(a, left, right);
        quickSort(a, left, k);
        quickSort(a, k+1, right);
    }
}

int partition(vector<Movie> &a, int left, int right)
{
//------------------------------------------------------
// partition(): rearrange a into 3 sublists:
// - a sublist a[left] ... a[j-1] of values at most a[j]
// - a sublist a[j], and
// - a sublist a[j+1] ... a[right] of values at least a[j]
//------------------------------------------------------
    string pivot = a[left].getTitle();
    int i = left - 1;
    int j = right + 1;
    do {
        do
        {
            j-- ;
        } while (a[j].getTitle().compare(pivot) > 0) ;
         
        do
        {
            i++ ;
        } while (a[i].getTitle().compare(pivot) < 0);
         
        if (i < j)
            exchange(a[i], a[j]);
             
    } while (i < j);
 
    return j;
}


int partitionYear(vector<Movie> &a, int left, int right)
{
//------------------------------------------------------
// partition(): rearrange a into 3 sublists:
// - a sublist a[left] ... a[j-1] of values at most a[j]
// - a sublist a[j], and 
// - a sublist a[j+1] ... a[right] of values at least a[j]
//------------------------------------------------------
    int pivot = a[left].getYear();
    int i = left - 1;
    int j = right + 1;
    do {
        do
        { 
            j-- ; 
        } while (a[j].getYear() > pivot);
        
        do
        { 
            i++ ; 
        } while (a[i].getYear() < pivot);
        
        if (i < j)
            exchange(a[i], a[j]);
            
    } while (i < j);
    
    return j;
}
void quickSortYear(vector<Movie> &a)
{
//------------------------------------------------------
// driver subprogram to sort an entire vector into
// ascending order with quickSort.
//------------------------------------------------------
    quickSortYear(a, 0, a.size()-1);
}

//----------------------------------------------------------------------------
//
void quickSortYear(vector<Movie> &a, int left, int right)
{
//------------------------------------------------------
// quickSort(): a recursive partitioning-based sort
//------------------------------------------------------

    if (left < right)
    {
        int k = partitionYear(a, left, right);
        quickSortYear(a, left, k);
        quickSortYear(a, k+1, right);
    }
}


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1