@ 병합 정렬(위키피디아)
병합 정렬은 집합을 n등분 하는 것을 반복하여 더 이상 나눠지지 않을 때까지 나누고, 나눠진 부분집합들을 n개씩 다시 정렬하는 것을 반복하면서 하나의 집합이 될 때까지 병합해 가는 정렬 방법이다.
Pseudocode >>
mergeSort(a[],m,n)
if(a[m:n] 의 원소수 > 1) then {
전체 집합을 두개의 부분집합으로 분할
mergeSort(a[], m, middle)
mergeSort(a[], middle+1, n)
// merge(a[], m, middle, n)
merge(a[m:middle], a[middle+1:n])
}
end mergeSort()
merge(a[], m, middle, n)
i <- m
j <- middle + 1
k <- m
while(i <= middle && j >= n) do {
if a[i] <= a[j] then sorted[k] <- a[i]; i <- i+1
else sorted[k] <- a[j]; j <- j+1
k <- k+1
}
if i > middle then
for(t <- j ; t <= n ; t <- t+1, k <- k+1) do {
sorted[k] <- a[t]
}
else
for(t <- i ; t <= middle ; t <- t+1, k <- k+1) do {
sorted[k] <- a[t]
}
for(t <- m ; t <= n ; t <- t+1) do {
a[t] <- sorted[t]
}
end merge()
소스 >>
# 병합 정렬 구현
# 2009-03-18, Jung-taek Lim(Heart)
def swap_array_elem(array, idx1, idx2)
temp = array[idx1]
array[idx1] = array[idx2]
array[idx2] = temp
end
def make_example_array
array = [69, 10, 30, 2, 16, 8, 31, 22]
end
def print_array(array)
puts array.map {|x| x.to_s + " "}.to_s
end
def merge_sort(arr, m, n)
return false if m < 0 || n >= arr.length
if arr[m..n].length > 1
middle = (m + n) / 2
merge_sort(arr, m, middle)
merge_sort(arr, middle+1, n)
merge(arr, m, middle, n)
end
end
def merge(arr, m, middle, n)
sorted = []
i = m
j = middle + 1
k = 0
while(i <= middle && j <= n)
if arr[i] <= arr[j]
sorted[k] = arr[i]
i += 1
else
sorted[k] = arr[j]
j += 1
end
k += 1
end
if i > middle
while(j <= n)
sorted[k] = arr[j]
j += 1
k += 1
end
else
while(i <= middle)
sorted[k] = arr[i]
i += 1
k += 1
end
end
(m..n).each { |l| arr[l] = sorted[l - m] }
end
array = make_example_array
merge_sort array, 0, array.length - 1
print_array array
|
결과 >>
2 8 10 16 22 30 31 69
'Dev.Programming > DS/Algorithm' 카테고리의 다른 글
| 힙 정렬 - in Ruby (0) | 2009/03/18 |
|---|---|
| 기수 정렬 - in Ruby (0) | 2009/03/18 |
| 병합 정렬 - in Ruby (0) | 2009/03/18 |
| 셸 정렬 - in Ruby (0) | 2009/03/18 |
| 삽입 정렬 - in Ruby (0) | 2009/03/18 |
| 퀵 정렬 - in Ruby (0) | 2009/03/17 |
