We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Sorting
  4. Running Time of Algorithms
  5. Discussions

Running Time of Algorithms

Problem
Submissions
Leaderboard
Discussions

Sort 216 Discussions, By:

votes

Please Login in order to post a comment

  • ThatGaggiKid
    7 years ago+ 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

    17|
    Permalink
    View more Comments..
  • paulo_bonfleur
    2 years ago+ 2 comments

    Python 3:

    def runningTime(arr):
        count = 0
        for j in range(len(arr)):
            for i in range(j, len(arr)):
                if arr[j] > arr[i]:
                    count += 1
        return count
    
    14|
    Permalink
  • rohangz
    6 years ago+ 1 comment

    Can we count the number of shifts ewquired to sort the data i.e number of shifts without actually sorting the data?

    10|
    Permalink
  • zerotohero
    3 years ago+ 1 comment
    #python3
    def runningTime(arr):
        z=0
        if arr==sorted(arr):
            return (0)    
        else:
            for i in range(1,len(arr)):
                x=arr[i]
                for j in range(i):
                    if arr[j]>x:
                        (arr[i],arr[j])=(arr[j],arr[i])
                        z+=1
            
            return z
    
    6|
    Permalink
  • RodneyShag
    5 years ago+ 0 comments

    Java solution - passes 100% of test cases

    From my HackerRank solutions.

    import java.util.Scanner;
    
    public class Solution {
    
        public static void insertionSortShiftCounter(int[] array) {
            int shifts = 0;
            for (int i = 1; i < array.length; i++) {
                int j = i;
                int value = array[i];
                while (j >= 1 && array[j-1] > value) {
                    array[j] = array[j-1];
                    j--;
                    shifts++;
                }
                array[j] = value;
            }
            System.out.println(shifts);
        }
        
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            int s = scan.nextInt();
            int[] array = new int[s];
            for (int i = 0; i < s; i++) {
                array[i] = scan.nextInt(); 
            }
            insertionSortShiftCounter(array);
        }
    }
    

    Let me know if you have any questions.

    6|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature