読者です 読者をやめる 読者になる 読者になる

一日一プロ

ソートの安定性

バブルソートと選択ソート

using System;
using System.Collections.Generic;

namespace StalbeSort
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			int N;
			List<int> data = new List<int>();

			N = int.Parse(Console.ReadLine ());
			for (int i = 0; i < N; i++) {
				data.Add (int.Parse (Console.ReadLine ()));
			}

			Console.WriteLine ("Bubble");
			List<int> bubble = new List<int>(data);
			BubbleSort (bubble);

			Console.WriteLine ("Selection");
			List<int> selection = new List<int> (data);
			SelectionSort (selection);

			bool flg = true;
			for (int i = 0; i < data.Count; i++) {
				if (bubble [i] != selection [i]) {
					flg = false;
				}
			}

			if(flg == true){
				Console.WriteLine ("Stable");
			}else{
				Console.WriteLine("NotStable");
			}
		}

		public static void BubbleSort(List<int> data)
		{
			for (int i = 0; i < data.Count; i++) {
				int j = ( data.Count-1);
				while ((j-1) >= i){
					if( data [j-1] > data [j]) {
						int tmp = data [j-1];
						data [j-1] = data [j];
						data [j] = tmp;
					}
					j--;
				}
				DataPrint (data);
			}
		}

		public static void SelectionSort(List<int> data)
		{

			for (int i = 0; i < data.Count; i++) {
				int min = 999999;
				int tmp_idx = i;

				for (int j = i; j < data.Count; j++) {
					if (min > data [j]) {
						min = data [j];
						tmp_idx = j;
					}
				}
				if (i != tmp_idx) {
					int tmp = data [i];
					data [i] = data [tmp_idx];
					data [tmp_idx] = tmp;
				}
				DataPrint (data);
			}
		}

		public static void DataPrint(List<int> data)
		{
			for (int i = 0; i < data.Count; i++) {
				Console.Write ("{0},", data [i]);
			}
			Console.WriteLine ();
		}
	}
}

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

広告を非表示にする