[알고리즘]정렬-삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)

정렬 알고리즘 3번째 시간입니다.

삽입 정렬은 입력 상태에 따라 수행 시간이 달라지는 정렬입니다.

삽입 정렬의 최선의 경우, 즉 입력이 이미 정렬되어있는 경우는 시간복잡도가 O(n)으로 굉장히 빠릅니다.

거의 정렬된 상태에서는 다른 정렬 알고리즘보다 확실히 빨라집니다.

반면에 역으로 정렬된 입력에 대해서는 O(n^2)의 시간이 걸립니다.

삽입 정렬 컨셉

배열을 정렬된 부분(앞 부분)과 아직 정렬 안 된 부분(뒷 부분)으로 나누어,

정렬 안 된 부분의 가장 왼쪽 원소를 정렬된 부분에서 정렬되게 위치시키는 작업을 합니다.

이 작업을 정렬 안 된 부분이 없어질 때까지 반복합니다.

예시 입니다.

코드

def Insertion_sort(n)
    s = Array.new
    (1..n).each do |s_n|
        s << rand(15)
    end
    (1..n-1).each do |i|
        c=s[i]
        j=i-1
        while j>=0&&s[j]>c
            s[j+1]=s[j]
            j=j-1
        end
        s[j+1]=c
    end
    return s
end
sorted_num=Insertion_sort(gets.to_i)
sorted_num.each do |bs|
    puts bs   
end
 

6번째 줄에서 1부터 n-1까지 반복문을 돌려줍니다.

이는 정렬 안 된 부분 배열의 인덱스 반복문인데 가장 왼쪽, 즉 0번 인덱스는 정렬 되었다고 가정하고 돌립니다.

7번째 줄 변수 c는 s[i]로 정렬 안 된 부분의 가장 왼쪽 원소로 설정합니다.

다음 j= i-1로 정렬된 부분의 가장 오른쪽 원소, 즉 정렬 안 된 왼쪽 원소의 바로 앞 원소의 인덱스로 설정해줍니다.

이는 좌측 방향으로 삽입될 적절한 위치를 검색하기 위해서 입니다.

9번째 줄 while문의 조건입니다. j>=0&&s[j]>c

j가 0이상이거나(j는 배열의 인덱스이기 때문에 0 미만은 검색 하지 않음) 

j인덱스의 값이 c보다 크거나(자리 이동이 일어나는 조건, 작은 숫자가 앞에 있어야 하기 때문)

10번째 줄 s[j+1]=s[j] s[j]의 값보다 더 작은 숫자가 발견 돼서 한 칸 뒤로 자리를 이동해줍니다.

11번째 줄 j=j-1을 해서 더 왼쪽으로 탐색해줍니다.

13번째 줄 s[j+1]=c 비어 있는 자리에 c를 집어 넣어 줍니다. 

여기서 s[j+1]은 10번째 줄 s[j+1]과 다른 인덱스입니다. 

11번째 줄 j=j-1의 효과로 10번째 줄 기준으로는 s[j] 라고 생각하면 됩니다.

여기까지 작업하고 6번째 반복문으로 돌아가 정렬이 완료될 때까지 진행해줍니다.

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