Problem:

Explain insertion sort step by step ie printing each step line by line

**Input Format:**

unsorted array

**Output Format:**

sorted array

**Constraints:**

none

Sample Input

8 1 4 -2 6 3

Sample Output:

1 8 4 -2 6 3

1 4 8 -2 6 3

-2 1 4 8 6 3

-2 1 4 6 8 3

-2 1 3 4 6 8

1 8 4 -2 6 3

1 4 8 -2 6 3

-2 1 4 8 6 3

-2 1 4 6 8 3

-2 1 3 4 6 8

Explanations:-

Insertion sort will first sort first 2 elements, then 1st 3, then 1st 4 and so on

Solution:

@arr =split(" ",$str);

$len=@arr;

for($i=1;$i<$len;$i++)

{

$x = $arr[$i];

$j=$i-1;

while($j>=0 and $x<$arr[$j])

{

$tmp=$arr[$j];

$arr[$j]=$x;

$arr[$j+1]=$tmp;

$j--;

$c++;

}

foreach(@arr)

{

print "$_ ";

}

print "\n";

}

Tips:

Insertion sort is efficient for small set of data only. For bigger set, select some other sort algorithm.

## No comments:

## Post a Comment