Running Time of Algorithms

  • + 7 comments

    Hey, I got marked off because my sorting algorithm sorts using one less shift. It passed all the test cases except the last one because it sorts it using 1 less sort than your solution.

    My Code import java.util.; import java.io.; public class InsertionSort { public static void main(String[] arg) { // check how many items we have Scanner sc = new Scanner(System.in); int nums = sc.nextInt();

            if (nums == 0)
                    return;
    
            // get the unsorted integers into an array
            int[] array = new int[nums];
            for (int i = 0; i < nums; i++)
                    array[i] = sc.nextInt();
    
            // call the insertion sort mehtod
            insertionSort(array);
        }
    
        public static void insertionSort(int[] array)
        {
            int totalShifts = 0;
            int nSorted = 1; // the first n items are sorted
            int n = array.length; // total number of items in the array
            while (nSorted < n)
            {
                    // get the next item
                    int newInt = array[nSorted];
                    int i = 0;
                    // locate its position in smaller array
                    for (i = 0; i < nSorted; i++)
                        // if you find a smaller item in there, exchange the two
                        if (array[i] > newInt)
                        {
                            array[nSorted] = array[i];
                            array[i] = newInt; 
                            // make sure exchanging the two didnt make a new imbalance, continue searching through
                            newInt = array[nSorted];
                                        totalShifts++;
                        }
                    nSorted++;
            }
            // print total number of shifts
            System.out.print(totalShifts);
        }
    }
    

    The test case:

    4
    4 4 3 4
    

    My solutions output: 1

    The test case's output: 2

    Lost 5 hackos because my algorithm is more optimal :/ and gets the job done just as well