4
\$\begingroup\$

I have written code for insertion sort. I just want some feedback whether the above implementation is correct and can be improved.

public class InsertionSortNew {

    static int temp;


    public static void InsertionSort(int [] array){

        for(int i =0;i<=array.length-1;i++){

            int key = array[i];

            for(int j=i-1;j>=0;j--){


                if(key<array[j]){
                    temp = key;
                    array[j+1] = array[j];
                    array[j] = key;
                    key = array[j];

                }else{
                    break;
                }


            }
        }
    }
\$\endgroup\$
3
\$\begingroup\$

Code

First of all, please avoid having a static int temp: in case two or more threads call your insertion sort, they will interfere. Also, I would declare the constructor as private:

private InsertionSortNew() {}

Style

You abuse your code with empty lines. Usually people put empty lines before and after conditional blocks (if) and loops (for, while).

Performance

You can prune away like 60% of assignments in the inner loop as follows: first, you store the element being inserted; next, until sorted you keep moving the preceding larger integers one position to the right, and finally, you put the cached element into its correct position.

All in all, I had this in mind:

private InsertionSortNew() {}

public static final void sort(int [] array){
    for (int i = 1; i < array.length; ++i) {
        int key = array[i];
        int j;

        for (j = i - 1; j >= 0 && array[j] > key; --j) {
            array[j + 1] = array[j];
        }

        array[j + 1] = key; 
    }
}

..., which gives me these performance figures:


Original version took 2281.41 milliseconds.
rodde's version took 1581.65 milliseconds.
Equals: true

\$\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.