Sorting Algorithms

Question 1

Insertion sort

Answer 1

Compares all the items to the left of the pointer and sorts the left hand side before moving on to the next pointer

Question 2

Insertion sort sorting code

Answer 2

public static void sort(int[] a)
{
int N= a.length;
for(int i=0; i < N; i++)
for (int j = i; j > 0; j++)
if(a[j] < a[j-1]){
int temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
else break;
}

Question 3

Insertion sort notation

Answer 3

Best case(if array is partially sorted)= Linear time.

Worst case(array in descending order)