구 원트노/알고리즘

[알고리즘]정렬-선택 정렬(Selection Sort)

정렬-선택 정렬(Selection Sort)


선택 정렬은 정렬되어지지 않은 부분의 최솟값을 선택하여 교환하는 것을 반복해 전체를 정렬시키는 알고리즘입니다.

선택 정렬의 특징으로는 입력이 거의 정렬 안되었던지, 역으로 정렬되어 있다든지, 랜덤하게 되어있든 지 구분없이 

항상 일정한 시간복잡도를 보인다는 점입니다.


선택 정렬 컨셉


오름차순 기준입니다. 

입력 값을 배열에 집어넣습니다.

그리고 배열 전체의 값에서 최솟값을 구해내서 

그 최솟값과 배열의 첫번째 원소의 값과 교환합니다.

그 다음에는 최솟값이 구해진 첫번째 원소를 제외하고

남은 배열에서 다시 최솟값을 구해서 두번째 원소와 교환합니다.

이 작업을 마지막 까지 반복하면서 정렬을 하는 알고리즘입니다.


예시 입니다.





코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def Selection_sort(n)
    #무작위 요소 생성
    s = Array.new
    (1..n).each do |s_n|
        s << rand(15)
    end
    #선택 정렬 
    (0..n-2).each do |i|
        min=i
        for j in i+1..n-1
            if s[j]<s[min]
             min=j
            end
        end
        s[i],s[min]=s[min],s[i]
    end
    return s
end
sorted_num=Selection_sort(gets.to_i)
sorted_num.each do |bs|
    puts bs   
end
cs


루비로 구현했습니다.

8번째 줄부터 보자면 1번째 반복문이 나옵니다.

이건 최솟값을 찾는 작업에 대한 반복문이고 (배열의 크기 -1)번 반복해야 합니다.

여기서 범위를 0에서 배열 크기 -2까지 둔 이유는 이 i최솟값과 교환하게 될 자리의 인덱스로 설정하기 위해서 입니다.

배열이기 때문에 인덱스의 시작은 0이고 마지막은 (배열.size-1)인데 마지막 인덱스는 교환할 상대가 없기 때문에 그 앞인 -2까지 선언하시면 됩니다.

9번째 줄에서 min 에다 i의 값을 넣습니다.

이 작업은 후에 나올 최솟값을 찾는 작업에서 사용될 최솟값 초기화 작업이라고 생각하시면 됩니다.

10번째 줄 반복문은 최솟값을 구하는 반복문입니다.

최솟값의 인덱스를 구하는 작업인데 범위를 보시면 i+1에서 n-1까지 이고  

i부터 하지 않은 이유는 현재 i값은 초기 상태의 최솟값이니깐 범위에 포함시키지 않은 것입니다.

이후 i의 값과 구해진 최솟값을 교환하는 걸로 끝이 납니다.

이상 선택 정렬 코드 분석을 마치겠습니다.


궁금하신 점 있으시면 댓글 남겨주세요!!