Sorting Algorithms Flashcards
1
Q
Insertion sort
A
Compares all the items to the left of the pointer and sorts the left hand side before moving on to the next pointer
2
Q
Insertion sort sorting code
A
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;
}
3
Q
Insertion sort notation
A
Best case(if array is partially sorted)= Linear time.
Worst case(array in descending order)