0
\$\begingroup\$

I have tested this code and it yields the expected outputs, but I want to verify if I have applied insertion sort algorithm correctly or not.

 import java.util.*;
public class InsertionSort 
{
    static void swap(int[] arr, int i, int j)
    {
        int temp = arr[i]; 
        arr[i] = arr[j]; 
        arr[j] = temp; 
    }

    static void sorter(int arr[])
    {

        int hole; 
        int n = arr.length; 
        if(n>=2)
        {
            for(int i = 1; i<n ; i++)
            { 
                hole = i;
                inner:
                for(int j = i-1; j>=0; j--)
                {
                    if(arr[j]> arr[hole])
                    {
                        swap(arr, j, hole);
                        hole = j; 
                    }
                    else
                        break inner; 
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
\$\endgroup\$

migrated from stackoverflow.com Feb 16 at 12:05

This question came from our site for professional and enthusiast programmers.

  • 2
    \$\begingroup\$ Do you want to ascertain correctness or Elegance? Correctness can be found by tests. \$\endgroup\$ – Sid Feb 16 at 9:45
  • \$\begingroup\$ You should follow the Java Naming Conventions: variable names always start with lowercase. Arr should be arr. \$\endgroup\$ – MC Emperor Feb 16 at 9:46
  • \$\begingroup\$ @MCEmperor Sure, fixing that right now. \$\endgroup\$ – Abcd Feb 16 at 9:47
  • \$\begingroup\$ You can check for such answers online geeksforgeeks.org/insertion-sort \$\endgroup\$ – Abdul Wasey Feb 16 at 9:48
  • 1
    \$\begingroup\$ It's correct, but it's far from good code. There is no need for n as intermediate variable, if (n>=2) is redundant, because it will just loop once in this case. The label inner is redundant in this case. And in general, if you ever feel you need to use a label in Java, you should restructure your code. And, finally, printing the result should not be done in the sort method. \$\endgroup\$ – wvdz Feb 16 at 10:04
3
\$\begingroup\$

Labeled loops

You say

                        break inner;

But that's not necessary. The inner loop is already the innermost loop. You could just say break;.

And frankly, you could have just said

                for (int j = i-1; j >= 0 && arr[j] > arr[hole]; j--)

No break or internal if needed.

But that's not the question you really wanted answered.

Insertion sort?

It's similar to an insertion sort. Your insertion method is a bit odd though. Normally insertion sort would find the insertion point and then move the elements after that. You're bubbling the current value forward.

Consider

int j = i - 1;
while (j >= 0 && numbers[j] < numbers[i]) {
    j--;
}

int temp = numbers[i];
for (int k = i; k > j; k--) {
    numbers[k] = numbers[k - 1];
}

numbers[j] = temp;

That does about half as many array assignments as your method.

Naming

I prefer a descriptive name like numbers to a generic abbreviation like arr. At minimum, it should be array. But I prefer numbers.

    static void sorter(int arr[])

As a general rule, we name classes and objects with noun names. Methods get verb names. So

    static void sort(int[] numbers) {

In Java, we also normally write arrays as int[] name not int name[].

You could name the class

class InsertionSorter {

Although in this case InsertionSort can be used as a noun.

Wildcard imports

import java.util.*;

The general policy is to import one class at a time, not a wildcard group. That's especially true here, since it's not clear that you are using any java.util classes.

Mixing logic and display

It's generally agreed that it is better to return the data and display it separately. Since you are sorting in place, that could just look like

InsertionSort.sort(numbers);
System.out.println(Arrays.toString(numbers));

Declare at initialization

You have

                hole = i;

You could do

                int hole = i;

It's generally considered best practice to declare variables as late as possible. You don't use hole outside the loop or across iterations, so there's no need to declare it outside the loop.

Redundant logic

        if(n>=2)
        {
            for(int i = 1; i<n ; i++)

If n is 1 or less then 1 < n will be false and it won't enter the loop.

And you don't need n. You can just say numbers.length whenever you need that value.

Standard methods

You could also replace these two loops with Java standard methods.

        int insertionPoint = Arrays.binarySearch(numbers, 0, i, numbers[i]);
        if (insertionPoint < 0) {
            insertionPoint = -insertionPoint - 1;
        }

        int temp = numbers[i];
        System.arraycopy(numbers, insertionPoint, numbers, insertionPoint + 1, i - insertionPoint);
        numbers[insertionPoint] = temp;

Of course, it's possible that you were trying to avoid standard methods. After all, Arrays.sort would solve this problem without additional coding.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.