Description In the first lab assignment, your job is to implement insertion-sort
ID: 3881343 • Letter: D
Question
Description In the first lab assignment, your job is to implement insertion-sort (Yes, this is just a warm-up, and the labs will be increasingly difficult. So heads up!) Input structure The input starts with an integer number which indicates the number of elements (integers) to be sorted, n. Then, the elements follow, one per line Output structure Recall that Insertion Sort first sorts the first two elements (in non-decreasing order), then the first three elements, and so on. You are asked to output the snapshot of the array at the end of each iteration. More precisely, for each 2Explanation / Answer
Hi ,
Please find below program in c for insertion sort. The program uses a link list.save below code in main.c. Compile and run file. Provide appropriate input as mentioned in question.
/* C program for insertion sort*/
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct Node
{
int data;
struct Node* next;
};
// Function to insert a given node in a sorted linked list
void sortedInsert(struct Node**, struct Node*);
// function to sort a singly linked list using insertion sort
void insertionSort(struct Node **head_ref)
{
// Initialize sorted linked list
struct Node *sorted = NULL;
// Traverse the given linked list and insert every
// node to sorted
struct Node *current = *head_ref;
while (current != NULL)
{
// Store next for next iteration
struct Node *next = current->next;
// insert current in sorted linked list
sortedInsert(&sorted, current);
//print steps
struct Node *temp = sorted;
while(temp != NULL)
{
printf("%d;", temp->data);
temp = temp->next;
}
printf (" ");
// Update current
current = next;
}
// Update head_ref to point to sorted linked list
*head_ref = sorted;
}
/* function to create a sorted link list*/
void sortedInsert(struct Node** head_ref, struct Node* new_node)
{
struct Node* current;
/* Special case for the head end */
if (*head_ref == NULL || (*head_ref)->data >= new_node->data)
{
new_node->next = *head_ref;
*head_ref = new_node;
}
else
{
/* Locate the node before the point of insertion */
current = *head_ref;
while (current->next!=NULL &&
current->next->data < new_node->data)
{
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
/* function to insert a node at the beginning of linked list */
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = (struct Node*)malloc(sizeof (struct Node* ));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
// Driver program to test above functions
int main()
{
struct Node *a = NULL;
int n;
scanf("%d",&n);
int i=0;
int num;
for(i=0;i<n;i++){
scanf("%d",&num);
push (&a,num);
}
insertionSort(&a);
return 0;
}