Writing insertion sort in an alternative way.

[bxdin]

I was able to come up with a successful algorithm to sort a lnked list's index.

void listSort(struct listNode *head)
{
    struct listNode *i,
                    *j,
                    *min;
    i = head->next;
    while (i->next != NULL)
    {
        min = i;
        j = i->next;
        while (j->next != NULL)
        {
            if (*(j->next) < *(min->next))
                min = j;

            j = j->next;
        }
        
        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;
    
    }        
}

Now what I would like to do is: use a break statement wihtin the, if statement, to escape the while loop.

But I'm really stuck.

This is the farthest that I have been able to reach:

void listSort(struct listNode *head)
{
    struct listNode *i,
                    *j,
                    *min;
    i = head->next;
    while (i->next != NULL)
    {
        min = i;
        j = i->next;
        while (j->next != NULL)
        {
            if (*(j->next) < *(min->next))
                break;

            min = j->next;        //This may be wrong.
            //min = j->next;    //no difference.
        }
        
        //listNode *temp1, *temp2, *temp3;
        
        //temp1 = i->next;
        i->next = min->next;
        //temp2 = min->next;
        //temp3 = min->next->next;

        min->next = j->next; // temp1;    

        //temp2->next = temp1->next;
        //temp1->next = temp3;
        i = i->next;
    
    }        
}

This is what the "sorted list" display: 0 1 4 8 7

Instead of the following 9 total number: 0 1 2 3 4 5 6 7 8 9

This is the full code

#include <iostream>
#include <string>
#include <sstream>

using namespace std;

struct listNode {
    int val;
    struct listNode *next;
    bool operator<(const struct listNode &n2) const {
        return this->val < n2.val;
    }
    bool operator>(const struct listNode &n2) const {
        return this->val > n2.val;
    }
};

struct listNode *newListNode(int val);
void deleteList(struct listNode *);
bool nodeSwap(struct listNode *, struct listNode *);
void listSort(struct listNode *head);
void printList(struct listNode *);
 
int main(int argc, char *argv[]) {
    struct listNode *head,*p;

	int SIZE = 10;
	int n[] = { 0, 2, 1, 5, 4, 3, 6, 8, 9, 7};


	p = head = newListNode(-1);
	for(int i = 0; i < SIZE; i++)
	{
        p->next = newListNode(n[i]);
        p = p->next;
	}


    cout << endl;
    printList(head);
    cout << "sorted ascending ..." << endl;
    listSort(head);
    printList(head);

	deleteList(head);

	system("pause");
    return 0;
}



void listSort(struct listNode *head)
{
    struct listNode *i,
					*j,
					*min;
	i = head;
	while (i->next != NULL)
	{
        min = i;
		j = i->next;
		while (j->next != NULL)
		{
			if (*(j->next) < *(min->next)) 
				break;

			min = j->next;		//This may be wrong.
			//min = j->next;	//no difference.
		}
		
		//listNode *temp1, *temp2, *temp3;
		
		//temp1 = i->next;
        i->next = min->next;
		//temp2 = min->next;
		//temp3 = min->next->next;

        min->next = j->next; // temp1;	

		//temp2->next = temp1->next;
		//temp1->next = temp3;
		i = i->next;
	
    }    	
}

struct listNode *newListNode(int val) 
{
    struct listNode *n = new listNode;
    n->val = val;
    n->next = NULL;
    return n;
}

void deleteList(struct listNode *head) {
    struct listNode *p = head, *q;
    while (p != NULL) 
	{
        q = p->next;
        free(p);
        p = q;
    }
}

[ne555]

Your first snip looks like `selection sort'
However, I would like an explanation of the structure as

    i = head->next;
    while (i->next != NULL)

looks incorrect (¿why are you sure that can dereference head->next?)

For the second snip ¿what are you trying to do?

[bxdin]

I'm trying to sort:0, 2, 1, 5, 4, 3, 6, 8, 9, 7, in ascending order.

Doing: while (i != NULL) results in an error, with the nested while loop failing to execute.
So, I stick with, due to better results: while (i->next != NULL)

You could say I'm trying to do insrtion sort, after having success with selection sort.

Only half the the numbers display.

[ne555]

Doing: while (i != NULL) results in an error, with the nested while loop failing to execute.
So, I stick with, due to better results: while (i->next != NULL)

Test with an empty list
Test with the first element out of order.

Second snip

while (j->next != NULL){
   //code that does not modify `j' or `j->next'
}

The logic is way off. Do this auxiliar function void inorder_insert( listNode *begin, listNode *end, listNode *value );
that would insert the value in the list that goes from begin to end (that's sorted) in the place where it should be.


As you are not doing `selection sort', having a `min' variable is obfuscated.

[bxdin]

The assignment requires the pre-existing nodes in the linked list to be re-arranged, by a sort function.

Selection/Insertion sort or whatever I don't care. My point is, I'm trying to get the algorithm to work using a break statement in the if statement.

I already, I got the algorithm to work perfectly, without a break statement, in my first post.
Now I'd like to learn how to get the algorithm to work using a break statement.

By the way in line 58, I have changed it to: i = head;