HackerRank Running Time of Algorithms Solution
In this post, we will solve HackerRank Running Time of Algorithms Solution.
In a previous challenge you implemented the 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 N.
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 algorithm.
Analysis of Insertion Sort
For each element V in an array of N numbers, Insertion Sort compares the number to those to its left until it reaches a lower value element or the start. At that point it shifts everything to the right up one and inserts V 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 N 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 N numbers will therefore take 1+2+…+(N − 1) operations, which is N(N-1)/2 (almost №2/2). Computer scientists just round that up (pick the dominant term) to N2 and say that Insertion Sort is an “N² time” algorithm.
What this means
The running time of the algorithm against an array of N elements is N². For 2N elements, it will be 4N2. Insertion Sort can work well for small inputs or if you know the data is likely to be nearly sorted, like check numbers as they are received by a bank. The running time becomes unreasonable for larger inputs.
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.
unction Description
Complete the runningTime function in the editor below.
runningTime has the following parameter(s):
- int arr[n]: an array of integers
Returns
- int: the number of shifts it will take to sort the array
Input Format
The first line contains the integern, the number of elements to be sorted.
The next line contains n integers of arr[arr[0]… arr[n-1]].
Sample Input
STDIN Function ----- -------- 5 arr[] size n =5 2 1 3 1 2 arr = [2, 1, 3, 1, 2]
Sample Output
4
Explanation
Iteration Array Shifts 0 2 1 3 1 2 1 1 2 3 1 2 1 2 1 2 3 1 2 0 3 1 1 2 3 2 2 4 1 1 2 2 3 1 Total 4
Running Time of Algorithms C Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
int ar_size;
scanf("%d", &ar_size);
int ar[ar_size], _ar_i;
for(_ar_i = 0; _ar_i < ar_size; _ar_i++) {
scanf("%d", &ar[_ar_i]);
}
int j;
int Count = 0;
for(_ar_i = 1; _ar_i < ar_size; _ar_i++) {
int Temp = ar[_ar_i];
for(j = _ar_i; j >= 0; j--) {
if (ar[j - 1] > Temp) {
ar[j] = ar[j - 1];
Count++;
}
else {
ar[j] = Temp;
break;
}
}
}
printf("%d\n", Count);
return 0;
}Running Time of Algorithms C++ Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
int n, a[1005], ans=0;
int main() {
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=1;i<n;i++){
int k=a[i],j=i;
for (;j>0 && a[j-1]>k;j--){
a[j] = a[j-1];
ans++;
}
a[j]=k;
}
printf("%d\n",ans);
return 0;
}Running Time of Algorithms C Sharp Solution
using System;
class Solution
{
/*
static void InsertionSort(int[] ar)
{
int i = ar.Length - 2;
int tmp = ar[i+1];
while (i >= 0 && ar[i] > tmp)
{
ar[i + 1] = ar[i];
foreach (int x in ar)
{
Console.Write("{0} ", x);
}
Console.WriteLine();
i--;
}
ar[i+1] = tmp;
foreach (int x in ar)
{
Console.Write("{0} ", x);
}
}*/
static void InsertionSort(int[] ar)
{
int shifts = 0;
for (int i = 1; i < ar.Length; i++)
{
int tmp = ar[i];
int j = i;
while (j > 0 && ar[j - 1] > tmp)
{
ar[j] = ar[j - 1];
shifts++;
j--;
}
ar[j] = tmp;
}
Console.WriteLine(shifts);
}
static void Main()
{
int t = int.Parse(Console.ReadLine());
string[] line = Console.ReadLine().Split();
int[] arr = new int[t];
for (int i = 0; i < t; i++)
{
arr[i] = int.Parse(line[i]);
}
InsertionSort(arr);
}
}Running Time of Algorithms Java Solution
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'runningTime' function below.
*
* The function is expected to return an INTEGER.
* The function accepts INTEGER_ARRAY arr as parameter.
*/
public static int runningTime(List<Integer> arr) {
int shiftCount = 0;
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr.get(i);
int j = i - 1;
while (j >= 0 && arr.get(j) > key) {
arr.set(j + 1, arr.get(j));
j = j - 1;
shiftCount++;
}
arr.set(j + 1, key);
}
return shiftCount;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int n = Integer.parseInt(bufferedReader.readLine().trim());
List<Integer> arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList());
int result = Result.runningTime(arr);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
}Running Time of Algorithms JavaScript Solution
function sortArrayValueByIndex(array, i) {
var moves = 0;
while (array[i-1] >= array[i] && array[i-1] != array[i]) {
moves++;
array.splice(--i, 2, array[i+1], array[i]);
}
return moves;
}
function getOutput(input) {
var rows = input.split('\n');
var n = parseInt(rows.shift(), 10);
var array = rows.shift().split(' ');
for (var i = 0; i < n; i++) {
array[i] = parseInt(array[i], 10);
}
var totalMoves = 0;
var index = array.length-1;
for (var i = 1; i < array.length; i++) {
totalMoves += sortArrayValueByIndex(array, i);
}
return totalMoves;
};
process.stdin.resume();
process.stdin.setEncoding('ascii');
var _input = '';
process.stdin.on('data', function (data) {
_input += data;
});
process.stdin.on('end', function () {
process.stdout.write(getOutput(_input));
});Running Time of Algorithms Python Solution
import sys
def print_list(data):
for element in data:
print(element, end=' ')
print()
length =int(sys.stdin.readline())
data = []
raw = sys.stdin.readline().split()
for index in range(length):
data.append(int(raw[index]))
counter = 0
for index in range(1, length):
element = data[index]
try:
for pointer in range(index,0,-1):
if data[pointer-1] <= element:
raise StopIteration('Place found!')
data[pointer] = data[pointer-1]
counter += 1
data[0] = element
except StopIteration:
data[pointer] = element
#print_list(data[case])
print(counter)Other Solutions
Good article. I will be going through many of these issues as well..