Hackerrank - Insertion Sort - Part 1

Popis problému
Celý popis zadania sa nacháza – Hackerrank.

Riešenie
Priraď posledný element do nejakej dočasnej premennej. Iteruj od posledného prvku k prvému (index 0).
Ak je aktuálny elemen väčší ako dočasná premenná, priraď do dočasnej premennej index aktuálneho prvku. Inak vymeň aktuálny element s predchádzajúcim.

Vytvoril som riešenie v týchto programovacích jazykoch:

Java
JavaScript
Scala
Ruby

Všetky riešenia sú dostupné aj na mojom GitHub profile.

Java

import java.util.*;

public class InsertionSort1 {
    
    public static void insertIntoSorted(int[] ar) {
        // Fill up this function
        int num = ar[ar.length - 1];
        boolean placed = false;
        for(int j = ar.length - 2; j >= 0; j--)
        {
            if(ar[j] > num)
            {
                ar[j + 1] = ar[j];
                printArray(ar);
            }
            else
            {
                ar[j + 1] = num;
                printArray(ar);
                placed = true;
                break;
            }
        }
        if(!placed)
        {
            ar[0] = num;
            printArray(ar);
        }
    }
    
    
/* Tail starts here */
     public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int s = in.nextInt();
        int[] ar = new int[s];
         for(int i=0;i<s;i++){
            ar[i]=in.nextInt(); 
         }
         insertIntoSorted(ar);
         in.close();
    }
    
    
    private static void printArray(int[] ar) {
      for(int n: ar){
         System.out.print(n+" ");
      }
        System.out.println("");
   }
    
    
}

import java.util.*;

public class InsertionSort1 {

public static void insertIntoSorted(int[] ar) {

// Fill up this function

int num = ar[ar.length - 1];

boolean placed = false;

for(int j = ar.length - 2; j >= 0; j--)

{

if(ar[j] > num)

{

ar[j + 1] = ar[j];

printArray(ar);

}

else

{

ar[j + 1] = num;

printArray(ar);

placed = true;

break;

}

if(!placed)

{

ar[0] = num;

printArray(ar);

}

/* Tail starts here */

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int s = in.nextInt();

int[] ar = new int[s];

for(int i=0;i<s;i++){

ar[i]=in.nextInt();

}

insertIntoSorted(ar);

in.close();

}

private static void printArray(int[] ar) {

for(int n: ar){

System.out.print(n+" ");

}

System.out.println("");

}

JavaScript

'use strict';

let insertIntoSorted = arr => {
    let num = arr[arr.length - 1];
    let placed = false;
    for(let j = arr.length - 2; j >= 0; j--) {
        if(arr[j] > num) {
            arr[j + 1] = arr[j];
            printArray(arr);
        } else {
            arr[j + 1] = num;
            printArray(arr);
            placed = true;
            break;
        }
    }
    if(!placed) {
        arr[0] = num;
        printArray(arr);
    }
};

let printArray = arr => console.log(arr.join(" "));

const processData = input => {
    let lines = input.split('\n');
    let arr = lines[1].split(' ').map(i => parseInt(i));
    insertIntoSorted(arr)
};

process.stdin.resume();
process.stdin.setEncoding("ascii");

var _input = "";
process.stdin.on("data", input => _input += input);
process.stdin.on("end", () => processData(_input));

'use strict';

let insertIntoSorted = arr => {

let num = arr[arr.length - 1];

let placed = false;

for(let j = arr.length - 2; j >= 0; j--) {

if(arr[j] > num) {

arr[j + 1] = arr[j];

printArray(arr);

} else {

arr[j + 1] = num;

printArray(arr);

placed = true;

break;

}

if(!placed) {

arr[0] = num;

printArray(arr);

}

};

let printArray = arr => console.log(arr.join(" "));

const processData = input => {

let lines = input.split('\n');

let arr = lines[1].split(' ').map(i => parseInt(i));

insertIntoSorted(arr)

};

process.stdin.resume();

process.stdin.setEncoding("ascii");

var _input = "";

process.stdin.on("data", input => _input += input);

process.stdin.on("end", () => processData(_input));

Scala

import scala.io.Source
import scala.util.control.Breaks._

object InsertionSort1 extends App {
  val lines = Source.stdin.getLines.toList
  val arr = lines(1).split(" ").map(_.toInt)

  insertIntoSorted(arr)

  def insertIntoSorted(arr: Array[Int]): Unit = {
    val insertionValue = arr(arr.length - 1)
    var placed = false
    breakable {
      Range(arr.length - 2, -1, -1).foreach(i => {
        if (arr(i) > insertionValue) {
          arr(i + 1) = arr(i)
          printArray(arr)
        } else {
          arr(i + 1) = insertionValue
          printArray(arr)
          placed = true
          break
        }
      })
    }
    if(!placed) {
      arr(0) = insertionValue
      printArray(arr)
    }
  }

  def printArray(arr: Array[Int]): Unit = {
    println(arr.mkString(" "))
  }
}

import scala.io.Source

import scala.util.control.Breaks._

object InsertionSort1 extends App {

val lines = Source.stdin.getLines.toList

val arr = lines(1).split(" ").map(_.toInt)

insertIntoSorted(arr)

def insertIntoSorted(arr: Array[Int]): Unit = {

val insertionValue = arr(arr.length - 1)

var placed = false

breakable {

Range(arr.length - 2, -1, -1).foreach(i => {

if (arr(i) > insertionValue) {

arr(i + 1) = arr(i)

printArray(arr)

} else {

arr(i + 1) = insertionValue

printArray(arr)

placed = true

break

}

})

}

if(!placed) {

arr(0) = insertionValue

printArray(arr)

}

def printArray(arr: Array[Int]): Unit = {

println(arr.mkString(" "))

}

Ruby

def print_array(arr)
  puts arr.join(" ")
end

def insertionSort(ar)
  num = ar[ar.size - 1]
  placed = false
  (ar.size - 2).downto(0) do |j|
    if(ar[j] > num)
      ar[j + 1] = ar[j]
      print_array(ar)
    else
      ar[j + 1] = num
      print_array(ar)
      placed = true
      break
    end
  end
  if(!placed)
    ar[0] = num
    print_array(ar)
  end
end

count = gets.to_i
ar = gets.strip.split.map {|i| i.to_i}

insertionSort(ar)

def print_array(arr)

puts arr.join(" ")

end

def insertionSort(ar)

num = ar[ar.size - 1]

placed = false

(ar.size - 2).downto(0) do |j|

if(ar[j] > num)

ar[j + 1] = ar[j]

print_array(ar)

else

ar[j + 1] = num

print_array(ar)

placed = true

break

end

if(!placed)

ar[0] = num

print_array(ar)

end

count = gets.to_i

ar = gets.strip.split.map {|i| i.to_i}

insertionSort(ar)

Pavol Pidanič

Dokážem na 10 prstoch napočítať do 1023

Hackerrank – Insertion Sort – Part 1