Sort I - Stable Sort http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_C

Main.java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public Main() {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        Card bArray[] = new Card[36];
        Card sArray[];


        for (int i = 0; i < n; i++) {
            String cardInfo = scan.next();
            bArray[i] = new Card(cardInfo.charAt(0), Integer.valueOf(cardInfo.substring(1, cardInfo.length())));
        }
        sArray = Arrays.copyOf(bArray, n);

        bubbleSort(n, bArray);
        selectionSort(n, sArray);

        printArray(n, bArray);
        System.out.println("Stable");
        printArray(n, sArray);
        if (isStable(n, bArray, sArray)) {
            System.out.println("Stable");
        } else {
            System.out.println("Not stable");
        }

    }

    public static boolean isStable(int n, Card[] cards1, Card[] cards2) {
        for (int i = 0; i < n; i++) {
            if (!cards1[i].equals(cards2[i])) {
                return false;
            }
        }
        return true;
    }

    public static void bubbleSort(int n, Card[] cards) {
        boolean flag = true;
        while (flag) {
            flag = false;
            for (int i = n - 1; i >= 1; i--) {
                if (cards[i].number < cards[i - 1].number) {
                    // 要素の交換
                    Card tmp = cards[i];
                    cards[i] = cards[i - 1];
                    cards[i - 1] = tmp;
                    flag = true;
                }
            }
        }
    }

    public static void selectionSort(int n, Card[] cards) {
        int minj;
        int i, j;
        for (i = 0; i < n - 1; i++) {
            minj = i;
            for (j = i; j < n; j++) {
                if (cards[minj].number > cards[j].number) {
                    minj = j;
                }
            }
            if (i != minj) {
                Card tmp;
                tmp = cards[i];
                cards[i] = cards[minj];
                cards[minj] = tmp;
            }

        }
    }

    // スペース区切りで表示
    public static void printArray(int n, Card A[]) {
        int i;
        for (i = 0; i < n - 1; i++) {
            System.out.print(A[i] + " ");
        }
        System.out.println(A[i]);
    }

    public class Card {
        public char suit;
        public int number;

        public Card(char suit, int number) {
            this.suit = suit;
            this.number = number;
        }

        @Override
        public String toString() {
            return suit + String.valueOf(number);
        }

        @Override
        public boolean equals(Object target) {
            if (this == target) {
                return true;
            }

            if (!(target instanceof Card)) {
                return false;
            }

            Card targetCard = (Card) target;
            return this.suit == targetCard.suit && this.number == targetCard.number;
        }
    }

    public static void main(String[] args) {
        new Main();
    }

}

Main.scala

import scala.io.StdIn

object Main extends App {
  val n = StdIn.readInt()
  val cardPattern = """(\w)(\d+)""".r
  val origList = StdIn.readLine().split(" ")
    .map { case cardPattern(suit, number) =>
    Card(suit.head, number.toInt)
  }.toList

  val bList = bsort(origList)
  val sList = ssort(origList)

  println(bList.mkString(" "))
  println("Stable")
  println(sList.mkString(" "))
  if (bList == sList) {
    println("Stable")
  } else {
    println("Not stable")
  }

  def foward(list: List[Card]): List[Card] = {
    if (list == Nil) {
      Nil
    } else {
      // もちろん list.min というListの最小値を求める関数もアリ
      val minValue = list.foldLeft(Int.MaxValue) { (preMin, n) =>
        Math.min(preMin, n.number)
      }
      if (list.head.number != minValue) {
        // 最小値を先頭にし、残りの要素は元のリストから最小値のdiff(集合の差)を取ったリスト。
        val minCard = list.filter(card => card.number == minValue).head
        minCard :: (list diff List(minCard))
      } else {
        list
      }
    }
  }

  def ssort(list: List[Card]): List[Card] = {
    list match {
      case Nil => Nil
      case List(x) => List(x)
      case xs =>
        foward(xs) match {
          case Nil => Nil
          case y :: ys =>
            y :: ssort(ys)
        }
    }
  }

  def bswap(list: List[Card]): List[Card] = {
    list match {
      case Nil => Nil
      case List(x) => List(x)
      case x :: xs =>
        bswap(xs) match {
          case Nil => Nil
          case y :: ys =>
            // swap
            if (x.number > y.number) {
              y :: x :: ys
            }
            else {
              x :: y :: ys
            }
        }
    }
  }

  def bsort(list: List[Card]): List[Card] = {
    list match {
      case Nil => Nil
      case List(x) => List(x)
      case xs =>
        // 最初のswap
        bswap(xs) match {
          case Nil => Nil
          // 先頭に最小値があるので、残りのリストに対してバブルソートし結合
          case y :: ys =>
            y :: bsort(ys)
        }
    }
  }
}

case class Card(suit: Char, number: Int) {
  override def toString = s"$suit$number"
}