current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite

I have come across a fun puzzle, sorting a linked list, and I wanted to go for quicksort. However, I am not quite sure whether my partitioning algorithm is efficient enough. I also believe that my code is not clean.

Is it possible to remove some variables or make it more efficient?

#include <iostream>
#include <cstdlib>

using namespace std;


struct Node
{
    int data;
    Node *next;
};

void printList(Node *list)
{
    Node *temp = list;
    while(temp != NULL)
    {
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}

int partition(Node *list, int start, int end)
{
    Node *startPtr = list, *endPtr = list, *head = list;

    for(int i = 0; i < start; i++)
        if(startPtr == NULL || startPtr->next == NULL)
            return -1;
        startPtr = startPtr->next;

    for(int i = 0; i < end; i++)
    {
        if(endPtr == NULL || endPtr->next == NULL)
            return -1;
        endPtr = endPtr->next;
    }


    Node *temp = NULL, *temp2 = startPtr;
    int pivot = endPtr->data;

    while(temp2->next != endPtr)
    {
        if(temp2->data < pivot)
        {
            if(temp != NULL)
                temp = temp->next;
            else
                temp = startPtr;

            swap(temp->data, temp2->data);
        }
        temp2 = temp2->next;
    }
    temp = temp->next;
    swap(temp->data, endPtr->data);

    int index;
    Node *temp3 = list;

    for(index = 0; temp3->data != pivot; index++)
        temp3 = temp3->next;

    return index;
}

int main()
{
    Node *a = new Node;
    Node *b = new Node;
    Node *c = new Node;
    Node *d = new Node;
    Node *e = new Node;
    Node *f = new Node;

    a->next = b;
    a->data = 2;
    b->next = c;
    b->data = 6;
    c->next = d;
    c->data = 3;
    d->next = e;
    d->data = 1;
    e->next = f;
    e->data = 7;
    f->data = 5;

    cout<<partition(a, 0, 5)<<endl;

    return 0;
}
share|improve this question
    
Can you please look at your code again? For me it looks like as if you forgot brackets in the first for loop in the function partition. –  Uwe Plonus Jul 2 '13 at 11:26
1  
I recommend fixing the indentation. That makes the code a lot more pleasant to read. –  Lstor Jul 2 '13 at 12:35
    
Please add a statement of the exact puzzle. Reading your code doesn't make it clear to me. Running it just prints '3'. And printList is unused... –  William Morris Jul 3 '13 at 13:49

1 Answer 1

up vote 2 down vote

Yeah, you're missing brackets, but I think I get what you're trying to do. If I'm wrong, ignore this obviously.

printList can just use a for-loop:

void printList(Node *list)
{

 for(Node *temp = list; temp != NULL; temp = temp->next;)
 {
    cout<<temp->data<<" ";
 }
}

Now for the partition function, you're always returning -1 if startPtr == NULL or endPtr == NULL. But you say that those point to what list points to (at the start of the function). In that case, just check if list is null first. Your function won't do anything if it is anyway:

if(list == NULL)
   return -1;

Now in those for-loops, all you have to do is check if startPtr->next and endPtr->next == NULL.

In your while loop, you have this code:

if(temp2->data < pivot)
{
    if(temp != NULL)
        temp = temp->next;
    else
        temp = startPtr;

    swap(temp->data, temp2->data);
}

But what if, for example, temp == NULL and temp2 == startPtr? Assuming swap() does what it says it does, you're unnecessarily swapping values. It might be expensive, and it might not be. I dunno. The function might also do something weird if you try to swap the same exact values. (As a side note, you're just passing the value of data. If swap doesn't take values by reference, you won't actually be doing anything to temp->data and temp2->data).

Also, in the declaration of your while loop, you're not checking for if temp2 == NULL.

while(temp2->next != endPtr) //This is will throw a Null Pointer Access Violation exception if temp2 == NULL

This could happen, because you aren't checking if temp2->next == NULL before you say temp2 = temp2->next. If it ever is, your loop will crash the program. I don't know if it's possible for temp2 to reach the end of the list, but if it is, you should just add a conditional.

After your while-loop, you have:

temp = temp->next;
swap(temp->data, endPtr->data);

That could potentially cause the same problems I described before.

Anyway, these are just suggestions. I didn't check thoroughly to see if there were variables you could remove, though.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.