Insertion Sorting Algorithm

Question

I am new to data structures and algorithms. I have just implemented an insertion sorting algorithm. I just want to make sure if my code is alright.

import java.util.Arrays; public class Main { public static void main(String[] args) { int[] test = {40, 1, 5, 0, 9}; for (int i = 0; i < test.length; i++) { for (int j = i - 1; j >= 0; j--) { if (test[i] < test[j]) { //swap if i is smaller than j . int temp = test[j]; test[j] = test[i]; test[i] = temp; /*we swap the j's value with i.we also have to check the other left items so we have to make i at the index where we just swapped.*/ i = j; } } } System.out.println(Arrays.toString(test)); } } 

Answer 1

Is it insertion sort

In short, no. But in longer, well it's clearly related to insertion sort, but still no.

This algorithm does the same sequence of swaps that a swap-based insertion sort would do (there is also a move-based version of insertion sort which is more efficient in practice). So that's it, case closed? Actually no, because this algorithm keeps resetting the loop variable of the outer loop, which is a behaviour that is normally not part of insertion sort, and it changes it in a fundamental way.

In terms of number of swaps, this algorithm (unnamed as far as I'm aware) still makes O(n²) swaps in the worst case. But I think it makes O(n³) comparisons, which is significantly worse than insertion sort.

Informally: let's assume the worst, that every next item is inserted all the way at the start of the sorted part of the array. Therefore, i is reset to zero after every insertion. Re-running the algorithm from zero up to the point where it just left off from takes O(n²) comparisons (but zero swaps, because the elements it's running over are already sorted), and since this happens n times, it's O(n³) comparisons in total. (to make that more proper I should say that the sum of i² from i=0 to i=n is a function of n contained in O(n³), but "informally"..)

Does it work though

Yes, but inefficiently.

What would make it insertion sort

If rather than changing i you instead compare and swap the positions j and j+1, the inner loop would do the same thing as it does now but without resetting i. That would make it an O(n²) algorithm that uses insertion as its strategy, so IMO that would qualify as insertion sort. Usually insertion sort is described having the inner loop stop when the comparison is false, but I don't think that continuing would make it not-insertion-sort, that would just make an inefficient implementation of insertion sort.