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.
  1. Counting Sort 3
  2. Discussions

Counting Sort 3

Sort by

recency

|

84 Discussions

|

  • ebeta922
     + 0 comments
    def counterForSortThree(arr):
    arr_counter = [0] * 100
    for j in arr:
        extracted_int = j.split()[0]
        arr_counter[int(extracted_int)] += 1
    return arr_counter


def countingSort3(arr):
    new_arr = counterForSortThree(arr)
    counter_result = 0
    result = []
    for i in range(0, len(new_arr)):
        while new_arr[i] > 0:
            counter_result += 1
            new_arr[i] -= 1
        result.append(counter_result)

    print(*result)

if __name__ == '__main__':
    n = int(input().strip())
    arr = []
    for i in range(n):
        arr.append(input())
    countingSort3(arr)

  • thinhproee
     + 0 comments
    import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[100];

        for (int i = 0; i < n; i++) {
            int val = scanner.nextInt();
            String s = scanner.next();
            arr[val]++;
        }

        int sum = 0;
        for (int i = 0; i < 100; i++) {
            sum += arr[i];
            System.out.print(sum + " ");
        }

        scanner.close();
    }
}

  • job_av
     + 0 comments

    IMHO while the target of this task is to show how pre-sorting is helpful for some other tasks, there is simple JS solution: 1) extract nums into additional array 2) sort asc this array (it doesn't matter how to do this, so I use built-in 'sort' method) 3) calc values in one loop 0..99 using results for previous array items

        let result = new Array();
    let num_arr = arr.map(value => value.split(' ')[0]);
    num_arr.sort((a,b)=>a-b);

    let j = 0;
        for (let i=0; i<100; i++){
    while (num_arr[j]<=i) j++;
    result[i] = j;
}

return result;

  • haiyennd13
     + 0 comments

    why my code is not correct? when i use intellij to run, result is correct, but when i copy code and paste it on hackerank is not correct? This is Kotlin Solution :

    import java.util.*

fun main(args: Array<String>) {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT. */
    val reader = Scanner(System.`in`)
    val n: Int = reader.nextInt()
    val arr2: Array<String> = Array(n) { " " }
    for (i in arr2.indices) {
        arr2[i] = readLine().toString()
    }
    countingSort(arr2)
}
fun countingSort(arr: Array<String>) {
    val numArr: Array<Int> = Array(arr.size) { 0 }
    for (i in arr.indices) {
        try {
            val numberOnly: String = arr[i].filter { it.isDigit() }
            numArr[i] = numberOnly.toInt()
        } catch (e: NumberFormatException) {
        }
    }
    val n = arr.size
    var max = Int.MIN_VALUE
    for (i in 0 until n) {
        max = maxOf(max, numArr[i])
    }
    val sum = Array(100) { 0 }
    val count: Array<Int> = Array(100) { 0 }
    for (i in 0 until n) {
        count[numArr[i]]++

    }
    var k = 1
    sum[0] = count[0]
    for (i in 1..99) {
        sum[k] = count[i] + sum[k - 1]
        k++
    }
    for (i in sum.indices) {
        print(sum[i].toString() + " ")
    }
}

  • KhanosVe
     + 0 comments

    javascript solution

    although the actual solution has nothing to do with the text, if you put the words in the right order it says:

    to be or not to be that is the question

    here's the code:

    function processData(input) {
  // strip out the strings and convert; only numbers matter
  const inputArr = input.split("\n").map((el) => el.split(" "));
  const n = parseInt(inputArr.shift()[0]); // Not used
  const numberArr = inputArr.map((el) => parseInt(el[0]));
  // const stringArray = inputArr.map(el => el[1]); // Not used

  // Finding the frequency of each number in the array
  const indexArray = new Array(100).fill(0);
  const frequencyArray = numberArr.reduce((acc, el) => {
    acc[Number.parseInt(el)]++;
    return acc;
  }, indexArray);

  // Creating the cumulative frequency array
  const bigL = frequencyArray.reduce((acc, el, index, arr) => {
    let count = 0;
    for (let i = 0; i < index + 1; i++) {
      count += arr[i];
    }
    acc.push(count);
    return acc;
  }, []);
  console.log(bigL.join(" "));
}

    to put the words in order, add this:

    // Putting the words in the correct order
const sortedList = frequencyArray.reduce((acc, el, index) => {
  if (el > 0) {
    for (let i = 0; i < el; i++) {
      acc.push(index);
    }
  }
  return acc;
}, []);
const inputMap = new Map();
for (let el of inputArr) {
  if (inputMap.has(el[0])) {
    inputMap.set(el[0], [...inputMap.get(el[0]), el[1]]);
  } else {
    inputMap.set(el[0], [el[1]]);
  }
}
const sortedWordsArray = sortedList.reduce((acc, el) => {
  const wordValue = inputMap.get(`${el}`);
  if (wordValue.length > 1) {
    acc.push(wordValue.shift());
    inputMap.set(`${el}`, wordValue);
  } else {
    acc.push(wordValue[0]);
    inputMap.delete(`${el}`);
  }
  return acc;
}, []);
console.log(sortedWordsArray.join(" "));