0
\$\begingroup\$

I have written basic insertion sort in java and I would request you to please spend some time on this code and give me your review of code. Is there anything I could have improved:

package elementarySorts;

public class InsertionSort {
    
    InsertionSort(int [] input_array){
        System.out.println("Unsorted arrey:");
        for(int elem:input_array) {
            System.out.print(elem +" ");
        }
        sort(input_array);
    }
    public void sort(int [] unsorted_array) {
        for(int i=0;i<unsorted_array.length;i++) {
            for(int j=i;j>=1;j--) {
                if(unsorted_array[j]<unsorted_array[j-1]) {
                    this.exchange(unsorted_array, j, j-1);
                }
            }
        }
        System.out.println("\nsorted arrey:");
        for(int elem:unsorted_array) {
            System.out.print(elem + " ");
        }
        
    }
    public void exchange(int [] inArray, int index1,int index2) {
        int temp=inArray[index1];
        inArray[index1]=inArray[index2];
        inArray[index2]=temp;
        
    
        
        
        
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
         int [] arr= {10,20,1,3,56,34,23};
        InsertionSort insort = new InsertionSort(arr);

    }

}

Hoping to hear your feedback.

\$\endgroup\$

2 Answers 2

2
\$\begingroup\$
    InsertionSort(int [] input_array){
        System.out.println("Unsorted arrey:");
        for(int elem:input_array) {
            System.out.print(elem +" ");
        }
        sort(input_array);
    }

This is a bad use of a constructor. This code should be moved into the main method.

Some quick rules of thumb:

  1. Don't produce output in a constructor (except for temporary debugging purposes).
  2. Don't perform actions in a constructor. Instead, perform the actions outside and pass the results to the constructor.

There may be circumstances where it is appropriate to violate these rules of thumb. But as a practical matter, if that happens, you should have comments explaining why it is necessary. In this case, I would say that it simply is not.

        System.out.println("\nsorted arrey:");
        for(int elem:unsorted_array) {
            System.out.print(elem + " ");
        }

Again, this should be done in the main method, not as part of the sorting process. Your method is doing two things. It's better practice to have it only do one thing.

Nitpick: you misspelled array in the println.

    }
    public void sort(int [] unsorted_array) {

This would be easier to read if there was a space between the closing } and the next method.

    }

    public static void sort(int [] unsorted_array) {

It's also better practice to declare methods that do not change state to static (which means that it can't change state).

Putting this and other tweaks together:

class InsertionSorter {

    public static void exchange(int[] data, int to, int from) {
        int temp = data[from];
        data[from] = data[to];
        data[to] = temp;
    }

    public static void sort(int[] data) {
        for (int i = 1; i < data.length; i++) {
            for (int j = i; j > 0; j--) {
                if (data[j] < data[j - 1]) {
                    exchange(data, j, j - 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] data = { 10, 20, 1, 3, 56, 34, 23 };
        System.out.println("Unsorted array:  " + Arrays.toString(data));
        sort(data);
        System.out.println("Sorted array:  " + Arrays.toString(data));
    }

}

We don't need to start the outer loop with 0, as the inner loop does nothing in that case. So we can start with 1.

This uses the built-in Arrays.toString rather than manually building your own.

Your class was not an insertion sort itself. Instead, it was the thing that did the sort. So I renamed it.

Algorithmically, it would probably be more efficient to say

    public static void sort(int[] data) {
        for (int i = 1; i < data.length; i++) {
            int j = i - 1;
            for (; (j >= 0) && (data[i] < data[j]); j--) {
            }
            j++;

            if (i > j) {
                int temp = data[i];
                System.arraycopy(data, j, data, j + 1, i - j);
                data[j] = temp;
            }
        }
    }

That changes the loop to just find the correct position and then moves all the elements at once rather than moving each twice. I haven't tested it, but that seems like it should be more efficient. It also may be more efficient to use System.arraycopy rather than doing it manually.

It also takes advantage of the fact that the array is sorted to stop looking once it has found the correct position. Your version will continue comparing even though it will always be false.

Of course, this is all reinventing the wheel. The simplest sort would be just

        Arrays.sort(data);

That would be easier to implement and almost certainly faster. But I'm assuming that you already knew that and wanted to implement your own.

\$\endgroup\$
0
\$\begingroup\$

Naming

A few comments on naming, in addition to mdfst13's review:

Packages should be named in a structured manner to avoid name collisions. The recommended way is to use some domain that you are associated to, e.g.

package com.stackexchange.gss.elementarySorts;

Java source code typically doesn't use underscores in names (with one exception: static final constants), so unsorted_array should better be named unsortedArray.

That name unsorted_array is misleading, as after the sort() call, its contents are sorted. So, IMHO arrayToBeSorted would be a better name, as that also hints at the fact that the array gets modified by the method, instead of returning a sorted copy of the original array.

No Work in constructors

I'm not completely in line with a rigorous "no actions in constructors" rule, but in your case it applies.

You class you've written can be understood as a "worker" specialized in the sorting of arrays. When constructing such a worker, you should prepare everything necessary for fulfilling such a task, and not have him fulfill such a task during construction. So, having the constructor already sort an array violates that rule.

Look at it from a caller's point of view (a sorting class hardly ever is used on its own, but as a helper within a more complex program). If you need to sort all rows of a 2-dimensional matrix, with your current class you can't write it the "logical" way:

int[][] matrix = ...;

InsertionSort sorter = new InsertionSort();
for (int rownum=0; rownum<matrix.length; rownum++) {
    int[] row = matrix[rownum];
    sorter.sort(row);
}

Instead, you have to write:

int[][] matrix = ...;

InsertionSort sorter = new InsertionSort(matrix[0]);
for (int rownum = 1; rownum < matrix.length; rownum++) {
    int[] row = matrix[rownum];
    sorter.sort(row);
}

This is weird, not only does it treat the first row differently than the following ones, but it also runs the risk of an ArrayIndexOutOfBoundsException, if the matrix has zero rows.

When creating a class, the structure should follow these guidelines:

  • What are the tasks of a class instance? These tasks should become methods of the class.
  • What needs to be prepared so a class instance can fulfill its tasks? That should go into the constructor (even if this means to do some computation, and that's where I disagree with the "no actions in constructors" rule).

So, I'd modify the "no actions in constructors" rule to read "prepare for work in the constructor, do the work in methods".

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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