### Writing insertion sort in an alternative way.

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

 ``123456789101112131415161718192021222324252627282930313233`` ``````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:

 ``12345678910111213141516171819202122232425262728293031323334`` ``````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
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104`` ``````#include #include #include 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; } }``````

Last edited on
Your first snip looks like `selection sort'
However, I would like an explanation of the structure as
 ``12`` `````` 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?
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.
Last edited on
 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
 ``123`` ``````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.
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;
Last edited on
Topic archived. No new replies allowed.