Converting a sort algorithm from for, to while loop

[coroshea]

The program works perfectly.

But in order for an individual to succeed in computer science, he or she must fiddle around with the program, and come up with other algorithms, such as converting a pre existing one, even it it is more or less efficient.

Again the program works perfectly.

The program, is to use a selection/ or insertion, sort algorithm, and sort a linked list of integers in ascending or descending order.

Here is the for loop version of the algorithm.

void listSort(struct listNode *head, SortOrder order)
{
    struct listNode *i,
                    *j,
                    *min;

    for (i = head; i->next != NULL; i = i->next) 
    {
        min = i;
        for (j = i->next; j->next != NULL; j = j->next) {
            if (order == ASCENDING) {
                if (*(j->next) < *(min->next)) min = j;
            } else {
                if (*(j->next) > *(min->next)) min = j;
            }
        }
        nodeSwap(i,min);
    }
}

Now, I'd like to convert both of those for loops to a while loop. For now though, I'm focusing on the outer/first for loop, an I am stuck.

void listSort(struct listNode *head, SortOrder order)
{
    struct listNode *i,
                    *j,
                    *min;

    //for (i = head; i->next != NULL; i = i->next) 
    i = head->next;     // I added this
    while (i)
    {
        min = i;
        for (j = i->next; j->next != NULL; j = j->next) 
        {
            if (order == ASCENDING) 
                if (*(j->next) < *(min->next)) min = j;
            else 
                if (*(j->next) > *(min->next)) min = j;            
        }

        i->next = i;    // I added this
        nodeSwap(i,min);        
    }
}

The program, only lists the original order of integers. Basically the program doesn't sort or display anything wihth the latter modification.

This is the nodeSwap function

bool nodeSwap(struct listNode *p, struct listNode *q) {
    struct listNode *t1, *t2, *t3;
    bool swapped = false;
    if (p != q) {
        t1 = p->next; t2 = q->next; t3 = q->next->next;
        p->next = q->next;
        q->next = t1;
        t2->next = t1->next;
        t1->next = t3;
        swapped = true;
    }
    return swapped;
}

[NathanOliver]

Line 8 needs to match the first par of your for loop. The codition of the while loop needs to match the condidtion of the while loop. The very last line of the while loop needs to match the last part of the for loop. In you case you need to switch lines 20 and 21

[coroshea]

I'm sorry, but your 1st two sentences doesn't make any sense.

I've also changed the while loop condition to i != Null, and swapped lines 20 & 21. The program still behaves the same as before. The last sentence seemed helpful though, thanks for that.

void listSort(struct listNode *head, SortOrder order)
{
    struct listNode *i,
                    *j,
                    *min;

    //for (i = head; i->next != NULL; i = i->next) 
    i = head->next;     // I added this
    while (i != NULL)
    {
        min = i;
        for (j = i->next; j->next != NULL; j = j->next) 
        {
            if (order == ASCENDING) 
                if (*(j->next) < *(min->next)) 
                    min = j;
            else 
                if (*(j->next) > *(min->next)) 
                    min = j;            
        }

        nodeSwap(i,min);
        i->next = i;    // I added this
    }
}

[NathanOliver]

Line 8 should be i = head. Line 9 should be while(i->next != NULL). Line 23 should be i = i->next

[coroshea]

Thanks you very much, sir!
Unfortunately now, the numbers are no longer being displayed in order.

The int_main had a function call:

        cout << "sorted ascending ..." << endl;
        listSort(head,ASCENDING);
        printList(head);
        cout << "sorting descending ..." << endl;
        listSort(head,DESCENDING);

There was a typedef under the #include header calls:

typedef enum { ASCENDING, DESCENDING } SortOrder;

This is the print function:

void printList(struct listNode *head) {
    struct listNode *p = head->next;

    cout << "List: ";
    while (p != NULL) {
        cout << p->val << ' ';
        p = p->next;
    }
    cout << endl << endl;
}

Anyway prior, to changing the for loops to a while loops, the program was able to display the following:

List: 0 2 1 3 4 5 9 6 8 8

sorted ascending...
List: 0 1 2 3 4 5 6 8 8 9

sorted descending...
List: 9 8 8 6 5 4 3 2 1 0

After the modification of the outer for loop to a while loop:

void listSort(struct listNode *head, SortOrder order)
{
    struct listNode *i,
                    *j,
                    *min;

    //for (i = head; i->next != NULL; i = i->next) 
    i = head;       // I added this
    while (i->next != NULL)
    {
        min = i;
        for (j = i->next; j->next != NULL; j = j->next) 
        {
            if (order == ASCENDING) 
                if (*(j->next) < *(min->next)) 
                    min = j;
            else 
                if (*(j->next) > *(min->next)) 
                    min = j;            
        }

        nodeSwap(i,min);
        i = i->next;    // I added this
    }
}

I got the following output:

List: 0 2 1 3 4 5 9 6 8 8

sorted ascending...
List: 8 8 2 1 3 4 5 9 6 0

sorted descending...
List: 8 8 2 1 3 4 5 9 6 0

[NathanOliver]

In you code you have this section now inside the second while loop.

if (order == ASCENDING) 
    if (*(j->next) < *(min->next)) 
        min = j;
else 
    if (*(j->next) > *(min->next)) 
        min = j;

You Would think that since the else is lined up with the first if that is what it is the else for but it is not. It is being treated as the else for the second if statement. This should get it working.

if (order == ASCENDING)
{
    if (*(j->next) < *(min->next)) 
        min = j;
}
else 
{
    if (*(j->next) > *(min->next)) 
        min = j;
}

[coroshea]

Thanks again for point out my careless mistake.

For my next objective, I was able to successfully transfer the swap block to the listSort function.

void listSort(struct listNode *head)//, SortOrder order)
{
    struct listNode *i,
                    *j,
                    *min;

    //for (i = head; i->next != NULL; i = i->next) 
    //i = head->next;       // I added this
    i = head;
    while (i->next != NULL)
    {
        min = i;
        j = i->next;
        while (j->next != NULL)
        {
            //if (order == ASCENDING) 
            {
                if (*(j->next) < *(min->next)) 
                    min = j;
            }
            j = j->next;
        }

        //nodeSwap(i,min);

        listNode *temp1, *temp2, *temp3;

        temp1 = i->next;
        i->next = min->next;
        temp2 = min->next;
        temp3 = min->next->next;
        min->next = temp1;  
        temp2->next = temp1->next;
        temp1->next = temp3;

        i = i->next;    // I added this

        //cout << " temp1 (original i->next): " << temp1 << " i->next after swap: " << &(i->next)   << " j: " << &j <<  " j->next: " << j->next << endl;
    }

}

I was wondering, if it would be possible to condense the following lines:

            listNode *temp1, *temp2, *temp3;

            temp1 = i->next;
            i->next = min->next;
            temp2 = min->next;
            temp3 = min->next->next;
            min->next = temp1;  
            temp2->next = temp1->next;
            temp1->next = temp3;

            i = i->next;    // I added this

To around 3 statements or so?

I was hoping something along the lines of maybe:

        //temp1 = i->next;
        i->next = min->next;
        //temp2 = min->next;
        //temp3 = min->next->next;
        min->next = j->next;    /// WRONG
        //temp2->next = temp1->next;
        //temp1->next = temp3;
        i = i->next;    // I added this

My main challenge I would say is, the 2nd one: min->next = j->next;
Orignally, it calls for the original value of, i->next (i.e temp1), before it is assigned to min->next.

I wouldn't mind modifying the inner while loop though.