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));
 }
}

• user555045: Which reference for how Insertion Sort is supposed to work did you follow? There is more than one algorithm that follows more or less the same principle but in a different way. This one doesn't match the versions I know about but it might match something else.
• Md Anik: I have tried to write the the algorithm, if the current position value (i) is smaller than previous index position j(i-1), then swap the value each time until It's sorted... I am newbie. So I cannot explain better. youtu.be/uMqVuEEWJv4 i followed this concept.

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(n2) swaps in the worst case. But I think it makes O(n3) 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(n2) comparisons (but zero swaps, because the elements it's running over are already sorted), and since this happens n times, it's O(n3) comparisons in total. (to make that more proper I should say that the sum of i2 from i=0 to i=n is a function of n contained in O(n3), 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(n2) 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.

• Md Anik: Thank you... Any tips for improving ds & algo? What approach and how should I learn them? I usually just try to realize the theories and apply them in my code without seeing professionals codes first...
• user555045: @MdAnik I think that's a good strategy, but reading the pseudocode would probably help, that's not the same as reading implementations it's just something to help with understanding how the concepts that are used in an algorithm fit together.
• Md Anik: So I should read/watch the theories and implementations at the first time? It's almost like memorizing codes?
• user555045: @MdAnik not implementations, but the pseudocode, that's not an implementation. Also I wouldn't recommend memorizing it, only looking at it to confirm your understanding.
• Md Anik: Thank you very much for your time.