So I have an assignment where I'm giving a random list of number and I need to sort them using insertion sort. I must use a singly linked list. I looked around at other posts but none seem to help. I get what insertion sort is but I just don't know how to write it in 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 dont know if this is right or what to do now
Let's think about how Insertion Sort works: It "splits" (in theory) the list into three groups: the sorted subset (which may be empty), the current item and the unsorted subset (which may be empty). Everything before the current item is sorted. Everything after the current item may or may not be sorted. The algorithm checks the current item, comparing it with the next item. Remember that the first item after the current item belongs to the unsorted subset.
Let's assume that you are sorting integers in increasing 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 begin sorting:
If the next item is greater than the current item, you don't need to sort that item. Just make it "current item" and continue.
If the next item is less than the current item then you have some work to do. First, save the next item somewhere - let's say in a pointer called temp - and then "remove" the next item from the list, by making current->next = current->next->next. Now, you need to find right place for the removed item. You can do this in two ways:
You continue this process until you reach the end of the list. Once you reach it, you know that you have completed your insertion sort and the list is in the correct sorted order.
I hope this helps.