Ruby实现的合并排序算法-Ruby

算法课的作业，利用分治法，合并排序。
				?

									#encoding: utf-8

									#author: xu jin, 4100213

									#date: Oct 27, 2012

									#MergeSort

									#to sort an array by using MergeSort algorithm

									#example output:

									#The original array is：[4, 32, 84, 58, 49, 40, 75, 29, 82, 21, 70, 37, 70]

									#The sorted array is: [4, 21, 29, 32, 37, 40, 49, 58, 70, 70, 75, 82, 84]

									MAX = 100

									arrayInt = Array.new

									for index in (0..12)

									 arrayInt[index] = rand(100) #produce 12 random number

									end

									puts "The original array is：" + arrayInt.to_s

									def merge(arr, left, middle, right)

									 arrL ,arrR = Array.new, Array.new

									 arrL[0..(middle - left)], arrR[0..(right - middle - 1)] = arr[left..middle], arr[middle + 1.. right]

									 arrL[arrL.size] ,arrR[arrR.size]= MAX, MAX

									 for k in (left..right)

									  arrL.first <= arrR.first ? (arr[k] = arrL.shift) : (arr[k] = arrR.shift)

									 end

									end

									def merge_sort(arr, left, right)

									 if left < right then

									  middle = (left + right)/2

									  merge_sort(arr, left, middle)

									  merge_sort(arr, middle + 1, right)

									  merge(arr, left, middle, right)

									 end

									end

									merge_sort(arrayInt, 0, arrayInt.length-1)

									puts "The sorted array is: " + arrayInt.to_s
Ruby实现的合并排序算法

相关文章

热门资讯
