2d example insertion sort

Insertion sort is a simple sorting algorithm: a comparision sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:

• Simple implementation
• Efficient for (quite) small data sets
• Adaptive (i.e., efficient) for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
• More efficient in practice than most other simple quadratic (i.e., O(n²)) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)
• Stable; i.e., does not change the relative order of elements with equal keys
• In-place; i.e., only requires a constant amount O(1) of additional memory space
• Online; i.e., can sort a list as it receives it

When humans manually sort something (for example, a deck of playing cards), most use a method that is similar to insertion sort.

Program:
#include <stdio.h>
#include <conio.h>
struct node
{
int number;
struct node *next;
};
struct node *head = NULL;
/* insert a node directly at the right place in the linked list*/
void insert_node(int value);
int main(void)
{
struct node *current = NULL;
struct node *next = NULL;
int test[] = {8, 3, 2, 6, 1, 5, 4, 7, 9, 0};
int i = 0;

/* insert some numbers into the linked list */
for(i = 0; i < i =" 0;">next != NULL)
{
printf("%4d\t%4d\n", test[i++], head->number);
head = head->next;
}

/* free the list */
for(current = head; current != NULL; current = next)
next = current->next, free(current);

return 0;
}

void insert_node(int value)
{
struct node *temp = NULL;
struct node *one = NULL;
struct node *two = NULL;

if(head == NULL) {
head = (struct node *)malloc(sizeof(struct node *));
head->next = NULL;
}

one = head;
two = head->next;

temp = (struct node *)malloc(sizeof(struct node *));
temp->number = value;

while(two != NULL && temp->number <>number) {
one = one->next;
two = two->next;
}

one->next = temp;
temp->next = two;
}

Posted in: C programming