Write a code to implement the insertion sort?

Answer 1

#include<stdio.h>

#include<conio.h>

void main()

{

int a[5]={5,2,8,9,4};

int i, k,temp;

for(i=0;i<5;i++)

{

for(k=i+1;k<5;k++)

{

if(a[i]>a[k])

{

temp=a[i];

a[i]=a[k];

a[k]=temp;

}

}

}

printf("\n sorted list=");

for(k=o;k<5;k++)

printf("%d",a[k]);

}

Answer 2

/*code for insertion sort*/

#include
#include
#include
#define max 20
void main()
{
int a[max],i,j,k=0,s,n;
clrscr();
printf("\n Enter the number of elements : ");
scanf("%d",&n);
for(i=0;i{
printf("\n Enter element %d] ",i+1);
scanf(" %d",&a[i]);
}
for(j=1;j{
k=a[j];
for(i=j-1;i>=0&&ka[i+1]=a[i];
a[i+1]=k;
s=i+1;
printf("\n Pass %d, Element insertetd in proper place : %d\n",j,k);
printf("\n Pass %d : ",j); // to see how elements get arranged as loop // counter increases
for(i=0;i{
printf(" %d ",a[i]);
}
printf("\n");
}
printf("\n sorted list is : \n");
for(i=0;iprintf(" %d ",a[i]);
printf("\n");
getch();
}

Answer 3

/* algorithm to perform insertion sort */

InsertionSort(A[0...n-1])

//sorts a given array by insertion sort

//input:array A[0..n-1]of n orderable elements

//output:array A[o..n-1]sorted in nondecreasing order

for i <-1 to n-1 do

v <- A[i]

j <- i-1

while j>=0 and A[j] > v do

A[j+1] <- A[j}

j <- j-1

A[j+1] <- v

Answer 4

Example for C++:

template<class T> void ListinsertSort(T * v, int n) { int * link = new int[n]; int head =0; int next,cur,i; link[0] = -1; for (i = 1 ; i < n; i++){ if (v[head] > v[i]){ link[i] = head; head = i; } else { for (cur = head ; cur != -1 && v[cur] <= v[i]; cur = link[cur]) next =cur; link[next] = i; link[i] = cur; } } cur = head; for ( i = 0 ;i < n;i++){ while(cur < i) cur = link [cur]; next = link[cur]; if (cur != i) { T swap = v[i]; v[i] = v[cur]; v[cur] = swap; link[cur] = link[i]; link[i] = cur; } cur = next; } delete[] link; }

Complexity is O(n2).

Answer 5

The following example demonstrates how to sort an array of pointers to strings. The code can be adapted to sort arrays of any type, including dynamic arrays, however it's best if the array contains pointers to objects rather than references to objects unless the object's size is not greater than that of a pointer, such as int or char. Larger objects take longer to copy which has a huge impact on performance.

Note also that insertion sort is ideal for comparatively small arrays. For larger arrays you should consider using quick sort, heap sort or merge sort instead.

#include <iostream>

int main()

{

// We'll be using 4 items throughout this example.

const int max = 4;

// Instantiate an array of unsorted pointers to literal strings.

char * names[max] = { "Hartley, John", "Evans, Steven", "Forbes, David", "Burns, Paul" };

printf( "Unsorted:\n");

for( int i=0; i<max; ++i )

printf( "%s\n", names[i] );

printf( "\n" );

// Note: insertion sort always begins at index 1, not index 0.

for( int index = 1; index < max; ++index )

{

// Copy the value at the current index. It's best if the array

// contains pointers as copying values can be costly.

char * value = names[index];

// The current index is now a "hole" in the array.

// It may move so we need to store it locally.

int hole = index;

// For the sake of clarity we'll also store the index of the

// element to the left of the hole (the previous element).

// This index will move as the hole moves.

int prev = hole - 1;

// Locate the insertion point by repeatedly comparing the previous

// element to the value we stored earlier (using string comparison).

// If the previous element is greater, move it into the hole, slide

// the hole to the left and repeat. The loop ends when the comparison

// is false, or the hole reaches the start of the array (index 0).

while( hole && strcmp( names[ prev ], value ) > 0 )

names[ hole-- ] = names[ prev-- ];

// Place the value in the hole.

names[ hole ] = value;

}

printf( "Sorted:\n" );

for( int i=0; i<max; ++i )

printf( "%s\n", names[i] );

printf( "\n" );

return(0);

}

Output:

Unsorted:

Hartley, John

Evans, Steven

Forbes, David

Burns, Paul

Sorted:

Burns, Paul

Evans, Steven

Forbes, David

Hartley, John

Answer 6

5