Using Insert Sort on a Separate List

Question

So, I have a job where I give a random list of numbers, and I need to sort them using insertion sort. I have to use a separate list. I looked at other posts, but no one seemed to help. I get what type of insertion is sorted, but I just don't know how to write it to code.

Node* insertion_sort(Node* head) { Node* temp = head_ptr; while((head->n < temp->n) && (temp != NULL)) temp = temp->next; head->next = temp->next; temp->next = head; head->prev = temp; } 

I do not know if this is right or what to do now

Answer 1

 struct node { int data; struct node *next; }; void insertion(struct node **head) { if((*head)== NULL || (*head)->next == NULL) { return; } struct node *t1 = (*head)->next; while(t1 != NULL) { int sec_data = t1->data; int found = 0; struct node *t2 = *head; while(t2 != t1) { if(t2->data > t1->data && found == 0) { sec_data = t2->data; t2->data = t1->data; found = 1; t2 = t2->next; } else { if(found == 1) { int temp = sec_data; sec_data = t2->data; t2->data = temp; } t2 = t2->next; } } t2->data = sec_data; t1 = t1->next; } } 

Answer 2

Think about how Sorting Sort works: it “splits” (theoretically) the list into three groups: a sorted subset (which may be empty), the current element, and an unsorted subset (which may be empty). Everything until the current item is sorted. Everything after the current item may or may not be sorted. The algorithm checks the current element by comparing it with the next element. Remember that the first item after the current item belongs to an unsorted subset.

Suppose you are sorting integers in ascending order (so given "3,1,5,2,4", you want to get "1,2,3,4,5"). You set your current item to the first item in the list. Now you start sorting:

If the next item is larger than the current, you do not need to sort this item. Just make it the "current item" and continue.

If the next element is smaller than the current element, then you have some work to do. First, save the next item somewhere — say in a pointer called temp — and then “remove” the next item from the list by doing the current-> next = current-> next-> next. Now you need to find the right place for the deleted item. You can do this in two ways:

• Or start at the beginning of the list, going forward until you find the right position. As soon as you do this, you insert the element there and continue to sort the insert. This is the easiest solution if you have a singly linked list.
• You go back until you find the right place for the item. As soon as you do this, you insert the element there and continue to sort the insert. This is a bit more, but may work well if you have a double-linked list.

You continue this process until you reach the end of the list. Once you achieve this, you know that you have finished sorting the insert, and the list is in the correct sort order.

Hope this helps.

Answer 3

Think about it - if the list is empty, temp will initially be NULL , so you will get undefined behavior when you do temp->next = head; .

Try debugging, this will surely help. You might also want to keep the previous node, so you can insert it later or look 2 nodes ahead.

Answer 4

 void linked_list::insertion_sort() { node * p = head; node * currentNode = head->next; // The node that is being compared at the moment. node * previousNode = head; // The node previous to the node being compared at the moment. //We can return from the sorting if the length of the linked list is less than 2. if (p == nullptr || p->next == nullptr) { return; } while (currentNode != nullptr) { //If the current node is larger than or equal to the largest element of the sorted linked list on the left, we can move to the next element. //Helpful for an already sorted array. if(previousNode->value<=currentNode->value){ currentNode = currentNode->next; previousNode = previousNode->next; } else{ //If the element is the smaller than the head element we need to take care of the head element. if (head->value > currentNode->value) { previousNode->next = currentNode->next; currentNode->next = head; head = currentNode; }else { p = head; while (p->next != NULL && p->next->value < currentNode->value) { p = p->next; } previousNode->next = currentNode->next; currentNode->next = p->next; p->next = currentNode; } } currentNode = previousNode->next; } }