ゴリゴリ、アルゴリズム学習(001)_マージソート

はじめに

学生時代はアルゴリズムの勉強を一生懸命やっていたのですが、pythonを覚えてしまってからは便利関数が多く、自分でアルゴリズムを組む必要がほとんどなくなってしまいました。
でも、最近どうにも行き詰まってしまい、それならと初心に戻ってアルゴリズムの勉強をやり直すことにしました。
そしてどうせなら、覚えた言語を一通り使って組んでみようと思います。
とりあえず、再帰を使うマージソートから。

python

mergesort.py

from array import array

def sort(array):
	# 配列の長さを計算する
	length = len(array)
	# 作業用の配列を作成する(zero配列)
	temp = [0]*length

	merge_sort(array, temp, 0, length-1)
	
def merge_sort(array, temp, left, right):
	if left < right:
		center = int((left+right)/2)
		# 左半分(left～center)
		# (*0)0-9, (*1)0-4, (*2)0-2, (3)0-1, (7)3-4
		# (*10)5-9, (*11)5-7, (12)5-6, (16)8-9
		merge_sort(array, temp, left, center)
		# 右半分(center+1～right)
		# (*4)0-1, (5)0-2, (*6)0-4, (*8)3-4, (*)0-9
		# (*13)5-6, (14)5-7, (15)5-9, (*17)8-9
		merge_sort(array, temp, center+1, right)
		# 整列および配列の結合
		# (3)0-1, (5)0-2, (7)3-4, (6)0-4, 
		# (12)5-6, (14)5-7, (16)8-9, (15)5-9, 
		# (8)0-9
		merge(array, temp, left, center+1, right)
	
def merge(array, temp, left, right, rightEndIndex):
	leftEndIndex = right-1
	tempIndex = left
	elementNumber = rightEndIndex-left+1
	#	(left,leftEndIndex),(right,rightEndIndex),tempIndex,elementNumber
	# (1) (0,0),(1,1),0,2
	# (2) (0,1),(1,2),0,3
	# (3) (3,3),(4,4),3,2
	# (4) (0,3),(1,4),0,5
	# (5) (5,5),(6,6),5,2
	# (6) (5,6),(6,7),5,3
	# (7) (8,8),(9,9),8,2
	# (8) (5,8),(6,9),5,5
	# (9) (0,8),(1,9),0,10
	while left<=leftEndIndex and right<=rightEndIndex:
		if array[left] <= array[right]:
			temp[tempIndex] = array[left]	# 左側要素を格納
			tempIndex += 1
			left += 1
		else:
			temp[tempIndex] = array[right]	# 右側要素を格納
			tempIndex += 1
			right += 1
	while left <= leftEndIndex:	# 左側の残り要素がある場合格納
		temp[tempIndex] = array[left]
		tempIndex += 1
		left += 1
	while right <= rightEndIndex:	# 左側の残り要素がある場合格納
		temp[tempIndex] = array[right]
		tempIndex += 1
		right += 1
	input(temp)
	for i in range(0,elementNumber):
		# ()内の数字が置き換え対象なので、indexはrightEndIndex(右端)から代入していく
		# (1) [(887, 995), 0, 0, 0, 0, 0, 0, 0, 0]
		# (2) [(831, 887, 995), 0, 0, 0, 0, 0, 0, 0]
		# (3) [831, 887, 995, (754, 787), 0, 0, 0, 0, 0]
		# (4) [(754, 787, 831, 887), 995, 0, 0, 0, 0, 0]
		# (5) [754, 787, 831, 887, 995, (323, 748), 0, 0, 0]
		# (6) [754, 787, 831, 887, 995, (322, 323, 748), 0, 0]
		# (7) [754, 787, 831, 887, 995, 322, 323, 748, (104, 322)]
		# (8) [754, 787, 831, 887, 995, (104, 322, 322, 323, 748)]
		# (9) [(104, 322, 322, 323, 748, 754, 787, 831, 887, 995)]
		array[rightEndIndex] = temp[rightEndIndex]
		rightEndIndex -= 1

def main():
	# 数値型に統一するため、listではなくarrayを利用
	sortTarget = array('i', [995, 887, 831, 787, 754, 748, 323, 322, 322, 104])

	# 整列前
	for eachValue in sortTarget:
		print(eachValue, ",", end="")
	print("\n")

	sort(sortTarget)

	# 整列前
	for eachValue in sortTarget:
		print(eachValue, ",", end="")
	print("\n")

if __name__ == "__main__":
	main()

C

mergesort.c

#include<stdio.h>

void sort(int array[], int length);
void mergeSort(int array[], int temp[], int left, int right);
void merge(int array[], int temp[], int left, int right, int rightEndIndex);
int main(void);

void sort(int array[], int length){
  int temp[length];
  mergeSort(array, temp, 0, length-1);
}

void mergeSort(int array[], int temp[], int left, int right){
  if(left<right){
    int center = (left+right)/2;
    // 左半分(left～center)
    mergeSort(array, temp, left, center);
    // 右半分(center+1～right)
    mergeSort(array, temp, center+1, right);
    // 整列および配列の結合
    merge(array, temp, left, center+1, right);
  }
}

void merge(int array[], int temp[], int left, int right, int rightEndIndex){
	int leftEndIndex = right-1;
	int tempIndex = left;
	int elementNumber = rightEndIndex-left+1;

  while(left<=leftEndIndex && right<=rightEndIndex){
    if(array[left] <= array[right]){
      temp[tempIndex++] = array[left++];
    }
    else{
      temp[tempIndex++] = array[right++];
    }
  }

  while(left<=leftEndIndex){
    temp[tempIndex++] = array[left++];
  }

  while(right<=rightEndIndex){
    temp[tempIndex++] = array[right++];
  }

  for(int i=0; i<elementNumber; i++){
    array[rightEndIndex] = temp[rightEndIndex];
    rightEndIndex--;
  }
}

int main(void){
  int sortTarget[] = {995, 887, 831, 787, 754, 748, 323, 322, 322, 104};
  int length = sizeof(sortTarget)/sizeof(sortTarget[0]);

  for(int i=0; i<length; i++){
    printf("%d, ", sortTarget[i]);
  }
  printf("\n");

  sort(sortTarget, length);

  for(int i=0; i<length; i++){
    printf("%d, ", sortTarget[i]);
  }
  printf("\n");

  return 0;
}

C++

mergesort.cpp

#include<iostream>
#include<string>

using namespace std;

void sort(int array[], int length);
void mergeSort(int array[], int temp[], int left, int right);
void merge(int array[], int temp[], int left, int right, int rightEndIndex);
int main(void);

void sort(int array[], int length){
  int temp[length];
  mergeSort(array, temp, 0, length-1);
}

void mergeSort(int array[], int temp[], int left, int right){
  if(left<right){
    int center = (left+right)/2;
    // 左半分に分割
    mergeSort(array, temp, left, center);
    // 右半分に分割
    mergeSort(array, temp, center+1, right);
    // ソート実行([left - center],[center+1 - right]の組で処理する)
    merge(array, temp, left, center+1, right);
  }
}

void merge(int array[], int temp[], int left, int right, int rightEndIndex){
  int leftEndIndex = right-1;
  int tempIndex = left;
  int elementNumber = rightEndIndex-left+1;

  while(left<=leftEndIndex && right<=rightEndIndex){
    if(array[left]<=array[right]){
      temp[tempIndex++] = array[left++];
    }
    else{
      temp[tempIndex++] = array[right++];
    }
  }

  while(left<=leftEndIndex){
    temp[tempIndex++] = array[left++];
  }
  while(right<=rightEndIndex){
    temp[tempIndex++] = array[right++];
  }

  for(int i=0; i<elementNumber; i++){
    array[rightEndIndex] = temp[rightEndIndex];
    rightEndIndex--;
  }
}

int main(void){
  int sortTarget[] = {995, 887, 831, 787, 754, 748, 323, 322, 322, 104};
  int length = sizeof(sortTarget)/sizeof(sortTarget[0]);

  // 整列前
  for(int i=0; i<length; i++){
    cout << sortTarget[i] << ",";
  }
  cout << "\n";

  sort(sortTarget, length);

  // 整列後
  for(int i=0; i<length; i++){
    cout << sortTarget[i] << ",";
  }
  cout << "\n";

  return 0;
}

JavaScript

mergesort.js

class MergeSort{
	sort(array){
		var temp = new Array(array.length);
		this.mergeSort(array, temp, 0, array.length-1)
	}
	mergeSort(array, temp, left, right){
		if(left<right){
			var center = parseInt((left+right)/2);
			// 左半分
			this.mergeSort(array, temp, left, center);
			// 右半分
			this.mergeSort(array, temp, center+1, right);
			// 配列の整列
			this.merge(array, temp, left, center+1, right);
		}
	}
	merge(array, temp, left, right, rightEndIndex){
		var leftEndIndex = right-1;
		var tempIndex = left;
		var elementNumber = rightEndIndex-left+1; // 要素数
		while(left<=leftEndIndex && right<=rightEndIndex){
			if(array[left]<=array[right])
				temp[tempIndex++] = array[left++];
			else
				temp[tempIndex++] = array[right++];
		}
		while(left<=leftEndIndex)	// 左の残り要素を格納
			temp[tempIndex++] = array[left++]
		while(right<=rightEndIndex)	// 右の残り要素を格納
			temp[tempIndex++] = array[right++]
		for(var i=0; i<elementNumber; i++){
			array[rightEndIndex] = temp[rightEndIndex];
			rightEndIndex--;
		}
	}
}

var sortTarget = [995, 887, 831, 787, 754, 748, 323, 322, 322, 104];
var mergeSort = new MergeSort();

// 変換前
for(var i=0; i<sortTarget.length;i++)
	process.stdout.write(sortTarget[i]+", ");
console.log("")

mergeSort.sort(sortTarget)

// 変換後
for(var i=0; i<sortTarget.length;i++)
	process.stdout.write(sortTarget[i]+", ");
console.log("")

終わりに

アルゴリズムは、考え方の練習なので、数学で言うなら解き方を学ぶものなので、サボっては駄目ですね。。。
今後定期的に学習していこうと思います。