I am an amazing person.

2 minute read

Running Time of Algorithms (Hacker Rank)

In the previous challenges you created an Insertion Sort algorithm. It is a simple sorting algorithm that works well with small or mostly sorted data. However, it takes a long time to sort large unsorted data. To see why, we will analyze its running time.

Running Time of Algorithms The running time of an algorithm for a specific input depends on the number of operations executed. The greater the number of operations, the longer the running time of an algorithm. We usually want to know how many operations an algorithm will execute in proportion to the size of its input, which we will call .

For example, the first two input files for Insertion Sort were small, so it was able to sort them quickly. But the next two files were larger and sorting them took more time. What is the ratio of the running time of Insertion Sort to the size of the input? To answer this question, we need to examine the Insertion Sort algorithm.

Analysis of Insertion Sort For each element in an array of numbers, Insertion Sort shifts everything to the right until it can insert into the array.

How long does all that shifting take?

In the best case, where the array was already sorted, no element will need to be moved, so the algorithm will just run through the array once and return the sorted array. The running time would be directly proportional to the size of the input, so we can say it will take time.

However, we usually focus on the worst-case running time (computer scientists are pretty pessimistic). The worst case for Insertion Sort occurs when the array is in reverse order. To insert each number, the algorithm will have to shift over that number to the beginning of the array. Sorting the entire array of numbers will therefore take operations, which is (almost ). Computer scientists just round that up (pick the dominant term) to and say that Insertion Sort is an “ time” algorithm.

running-time-picture

What this means As the size of an input () increases, Insertion Sort’s running time will increase by the square of . So Insertion Sort can work well for small inputs, but becomes unreasonably slow for larger inputs. For large inputs, people use sorting algorithms that have better running times, which we will examine later.

Challenge Can you modify your previous Insertion Sort implementation to keep track of the number of shifts it makes while sorting? The only thing you should print is the number of shifts made by the algorithm to completely sort the array. A shift occurs when an element’s position changes in the array. Do not shift an element if it is not necessary.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    public static int runningTimeAlgorithms(int[] unsorted){
        int count = 0;
        for(int i = 1; i < unsorted.length; i++){
            int j = i;
            int min = unsorted[i];
            while(j > 0 && min < unsorted[j-1]){
                int tmp = unsorted[j];
                unsorted[j] = unsorted[j-1];
                unsorted[j-1] = tmp;
                j--;
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] unsorted = new int[n];
        for(int i = 0; i < n; i++){
            unsorted[i] = in.nextInt();
        }
        int result = runningTimeAlgorithms(unsorted);
        System.out.println(result);
    }
}
행운의 77문제 프로젝트
  행운의 77문제 프로젝트는 한 달동안 알고리즘 문제 77개를 푸는 프로젝트입니다.

You may also enjoy