The insertion sort algorithm is a more efficient means of sorting an array than
ID: 3548022 • Letter: T
Question
The insertion sort algorithm is a more efficient means of sorting an array than the selection sort. This algorithm is analogous to the procedure that card players follow when picking up cards and inserting them in their hand to form a run in a particular suit. A player makes room for a new card by shifting over the ones that follow it and then inserting it where it belongs in the hand. In sorting an array, all values are available when you begin, but you can assume that the array is not sorted and start by inserting the value currently in the second array element by comparing it to the first element. This gives you a sorted subarray consisting of the first two elements. Next, you insert the value currently in the third array element where it belongs compared to the first two, which gives you a sorted subarray of three elements, and so on. You
Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node *next;
};
typedef struct node *List_type;
List_type getnode(); //function for getting the node memory
List_type insertion(List_type); //function for sorting
int main()
{
List_type head,q,sorted_array;
int N,i;
printf(" enter the size of the list to be sorted ");
scanf("%d", &N);
printf("enter the numbers ");
head = getnode();
scanf("%d",&(head->info));
q = head;
for( i=1;i<N;i++)
{
q->next = getnode(); //getting the required node memory
scanf("%d",&(q->next->info)); //scanning all the elemnts of list
q = q->next; //for scanning next element
}
q = head;
for( i=0;i<N;i++)
{
printf("%d ",q->info); // printing the list
q = q->next;
}
sorted_array = insertion(head); //sorting function
q = sorted_array;
printf(" sorted list is ");
for( i=0;i<N;i++)
{
printf("%d ",q->info); // printing the sorted list
q = q->next;
}
printf(" ");
} //main program ends
List_type getnode() //function for memory allocation
{
List_type p;
p = (List_type)malloc(sizeof(struct node));
p->next = NULL;
return p;
}
List_type insertion(List_type p)
{
List_type q, head, curr, prev;
head = p;
prev = p;
while(prev->next)
{
curr = prev->next;
if(curr->info>prev->info)
{ //case 1 :when current element is already larger than its previous.
if(curr->next!=NULL) curr = curr->next;
if(prev->next!=NULL) prev = prev->next; //do nothing, move ahead
}
if(curr->info < head->info) //case 2: when current element is smaller than the starting element
{
prev->next = curr->next;
curr->next = head;
head = curr; // make that small element as head or first element of the list
}
if(curr->info>head->info && curr->info<prev->info) //case 3: when curr element is in between the first and its prev.
{
q = head;
while(q!= prev)
{
if(q->next->info>curr->info)
{
prev->next = curr->next;
curr->next = q->next;
q->next = curr;
break;
}
q = q->next;
}
}
}
return head;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.