@ 삽입 정렬(위키피디아)
전체를 정렬된 부분집합/정렬되지 않은 부분집합 으로 나누고, 정렬되지 않은 부분집합을 하나씩 정렬된 부분집합으로 옮기는데, 옮기는 중에 정렬하여 위치를 정하는 방법이다.
Pseudocode >>
insertionSort(a[], n)
for(i <- 1 ; i < n ; i <- i+1) do {
temp <- a[i]
j <- i
if(a[j-1] > temp) then move <- true
else move <- false
while(move) do {
a[j] <- a[j – 1]
j <- j – 1
if(j > 0 and a[j-1] > temp) then move <- true
else move <- false
}
a[j] <- temp
}
end insertionSort()
소스 >>
# 삽입 정렬 구현
# 2009-03-17, 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 insertion_sort(array)
return false if array.length < 2
(1..array.length - 1).each do |i|
temp = array[i]
j = i
move = array[j-1] > temp ? true : false
while(move)
array[j] = array[j-1]
j = j-1
move = (j > 0 && array[j - 1] > temp) ? true : false
end
array[j] = temp
end
end
array = make_example_array
insertion_sort array
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/17 |
| 선택 정렬 & 버블 정렬 in Ruby (2) | 2009/03/17 |
| 그래프 탐색(깊이 우선 탐색, 너비 우선 탐색) - in Ruby (0) | 2009/03/16 |
