Skip to content

Instantly share code, notes, and snippets.

@yamadayuki
Created December 8, 2016 19:29
Show Gist options
  • Save yamadayuki/bcba6cb6c6fa8de9bc68fad8f8d36ba4 to your computer and use it in GitHub Desktop.
Save yamadayuki/bcba6cb6c6fa8de9bc68fad8f8d36ba4 to your computer and use it in GitHub Desktop.
Stable Sort
// 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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment