CODEWITHSUNDEEP
javaarrayssortinginsertion-sort
Shane
Shane

Reputation: 59

Java Insertion Sort

Below is main method calls the insertionSort method putting in multiple arrays of different sizes. I only have one array in this example but there are multiple that will be ran. I cannot figure out how to get arr2 to sort like an insertion sort would sort. Starting from the end of the arr2 pushing its way up until it reaches the correct point in the arr2 and then looking at the unsorted array again and putting the next number at the end of arr2 and then sorting it again and again until there is a sorted array.If you could help me with this it would be great. And yes, I have looked at other code but none help me with my problem, I have spent a week trying to figure this out.

static void insertionSort(int[] arr) {
    final long startTime = System.nanoTime(); // starts timer
    System.out.println("Insertion Sort");
    //************** Code For Sorting *****************//
    int[] sorted = Arrays.copyOf(arr, arr.length); // Copies unsorted array to new array
    Arrays.sort(sorted); // sorts unsorted array for comparison later on
    
    int[] arr2 = new int[arr.length];
    for(int h = 0; h < arr.length - 1; h++){// makes arr2 all 0's
        arr2[h] = 0;
    }
        
    arr2[arr2.length - 1] = arr[0];
    for(int k = 0; k < arr.length; k++){
        System.out.print(arr2[k] + ", ");
    }
    System.out.println();
    
    while(arr2 != sorted) {
        for(int i = 1; i < arr2.length; i++) {
            if(arr[i] < arr2[arr2.length-1]) {
                int last = arr2[arr2.length-1];
                int before = arr[i];
                arr2[arr2.length-1]= before;
                arr2[arr2.length-2]= last;
                
                // CANT FIGURE OUT HOW TO SORT CORRECTLY
            }

            for(int k = 0; k < arr.length; k++) {
                System.out.print(arr2[k] + ", ");
            }

            System.out.println();
        }
    }

    for(int k = 0; k < arr.length; k++) {
        System.out.print(arr2[k] + ", ");
    }
}

public static void main(String[] args) {  
    int arr[] = {}; // Array that will be put into each sort method
    //****************Multiple Arrays for testing*******************//
    
    /* ************All Arrays Are Whole Numbers 1-100***************
    arr1 = Array of size 20
***************************************************************  */
    int arr1[] = {6,3,20,10,11,2,9,1,19,17,4,16,8,15,18,14,5,7,12,13}; // {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
//**************************************************************//
    int arrayNumber = 1;
    while(arrayNumber < 2){
        if (arrayNumber == 1){
            arr = arr1;
        }
System.out.println("Array "+ arrayNumber +" Before Sorting");
        for(int i = 0; i < arr.length; i++){
            System.out.print(arr[i] + ", ");
        }
        System.out.println();
        //************* Array put into Methods***************//
 insertionSort(arr);
//***************************************************//
        arrayNumber++; // Adds 1 to arrayNumber to show next array
    }

}

Upvotes: 1

Views: 346

Answers (1)

wylasr
wylasr

Reputation: 117

at first arr2 can never == sorted .== means two Object have the same address in memory.and then, insert sort is sort a set of Object,and store them in a sorted collection,in your insertionSort(int[] arr) method,at least you need two array,your arr2 is a sorted array.but you need more space ,in another words,you can initialize arr2 = new int[arr.length*2];.and then just iterate arr .and insert arr[i] into right place.the right place is when you compare arr[i] with arr2[j] if arr[i]>= arr[j] && arr[i]<arr[j+1],index j is the right place .and then move all the element of arr2 between index j and last element of arr2,we said arr[k], not arr2.length-1,importantly,you should move arr2[k] first by one step ,just like arr[k+1]=arr[k];and from now on one Object was inserted into the arr2.

Upvotes: 1

Related Questions