Skip to content

Instantly share code, notes, and snippets.

@yamadayuki

yamadayuki/stable_sort.js

Created December 8, 2016 19:29
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save yamadayuki/bcba6cb6c6fa8de9bc68fad8f8d36ba4 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save yamadayuki/bcba6cb6c6fa8de9bc68fad8f8d36ba4 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. yamadayuki created this gist Dec 8, 2016.
    71 changes: 71 additions & 0 deletions stable_sort.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,71 @@
    // http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_C

    // Test Case
    // Input
    // 5
    // H4 C9 S4 D2 C3

    // Output
    // D2 C3 H4 S4 C9
    // Stable
    // D2 C3 S4 H4 C9
    // Not stable

    var input = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
    var n = +input.shift();
    var cards = input.shift().split(' ');

    function bubbleSort(input) {
    var cards = [].concat(input);

    for (var i = 0; i < cards.length; i++) {
    for (var j = cards.length - 1; j > i; j--) {
    if ((+cards[j][1]) < (+cards[j - 1][1])) {
    var tmp = cards[j];
    cards[j] = cards[j - 1];
    cards[j - 1] = tmp;
    }
    }
    }

    return cards;
    }

    function selectionSort(input) {
    var cards = [].concat(input);

    for (var i = 0; i < cards.length; i++) {
    var minIndex = i;
    for (var j = i; j < cards.length; j++) {
    if ((+cards[j][1]) < (+cards[minIndex][1])) minIndex = j;
    }

    if (minIndex !== i) {
    var tmp = cards[i];
    cards[i] = cards[minIndex];
    cards[minIndex] = tmp;
    }
    }

    return cards;
    }

    function isStable(bubble, selection) {
    if (bubble === selection) {
    return 'Stable';
    } else {
    return 'Not stable';
    }
    }

    function stableSort(cards) {
    var bubble = bubbleSort(cards).join(' ');
    var selection = selectionSort(cards).join(' ');

    console.log(bubble);
    console.log('Stable');
    console.log(selection);
    console.log(isStable(bubble, selection));
    }

    stableSort(cards);