정렬 알고리즘 (2) : 삽입 정렬, 버블 정렬

지난 시간에 이어 이번 글에서도 정렬 알고리즘에 대해 이어 설명하겠습니다.

이번 글에서는 삽입 정렬과 버블 정렬에 대해 소개하겠습니다. 

---

삽입 정렬 Insertion Sort

• 삽입 정렬의 개념

삽입 정렬은 현재 인덱스와 해당 인덱스보다 작은(왼쪽) 인덱스에 있는 원소들을 비교하여 자신이 들어갈 위치를 찾아 삽입하는 정렬 알고리즘 입니다. 

 

• 삽입 정렬의 기본 로직 

1. 0번째 인덱스는 가장 왼쪽에 위치해 있기 때문에 비교 대상이 없으므로 삽입 정렬은 1번재 인덱스부터 시작합니다. 
2. 삽입할 대상이 되는 현재 인덱스는 별도의 변수에 저장해 두고, 현재 인덱스에서 -1 한 인덱스의 원소들을 비교합니다. 
3. 현재 인덱스의 원소 값이 비교 인덱스의 원소 값보다 큰 원소를 만날때까지 비교 인덱스를 -1 씩 해주며 왼쪽으로 이동합니다.
4. 현재 인덱스 원소 값보다 큰 값을 가진 비교 인덱스를 만나면 해당 비교 인덱스의 +1 위치에 현재 인덱스 값을 삽입합니다. 
5. 현재 인덱스 값을 1씩 증가시키면서 위 1~4 과정을 반복합니다.
6. 모든 값들이 정렬된 상태에 도달하면 반복이 종료됩니다. 

• 삽입 정렬의 복잡도 

모든 원소들이 자신보다 큰 원소를 만날 때까지 비교해야 하지만 이미 정렬되어 있는 경우는 한 번의 비교만으로 자신보다 큰 값을 만나기 때문에 최고의 경우 아주 좋은 성능을 냅니다. 즉, 최선의 경우 시간 복잡도는 O(n)입니다. 그러나 최악의 경우 모든 값을 비교한 후, 삽입이 이루어지기 때문에 시간복잡도는 이전 글에서 설명한 선택 정렬과 마찬가지로 O(n^2)입니다. 

삽입 정렬 역시 in-place 알고리즘 이기 때문에 공간 복잡도가 O(n)입니다. 

• 삽입 정렬 Python3 구현 코드 

def insertion_sort(q,n):
		# 모든 원소 n개에 대하여 수행
    for i in range(1,n):
				# 삽입할 위치를 찾는 원소의 인덱스를 key에 저장
        key = i
				# key 왼쪽에 있는 모든 원소에 대하여 비교 수행
        for j in range(0,i):
						# key에 있는 원소가 자신보다 큰 비교 원소를 만나면
						# 해당 원소와 위치를 바꾼다. 
            if q[key] < q[j]:
                t = q[j]
                q[j] = q[key]
                q[key] = t

---

버블 정렬 Bubble Sort

• 버블 정렬의 개념

버블 정렬은 서로 인접한 두 원소를 검사하여 정렬하는 정렬 알고리즘 입니다.

선택정렬과 유사한 정렬 방식으로 오름차순을 기준으로 합니다. 

• 버블 정렬의 기본 로직

1. 첫번째 원소와 두번째 원소 비교를 시작으로 (마지막 - 1) 번째 원소와 마지막 원소를 비교합니다.
2. 인접한 두 원소를 비교할 때마다 큰 값을 오른쪽에, 작은 값을 왼쪽에 위치시킵니다. 
3. 1~2 과정이 1회전을 의미하며 이를 수행하고 나면 가장 큰 원소가 맨 뒤에 위치하게 되기 때문에 그 다음 번 회전에서는 맨 뒤에 있는 원소를 제외하고 나머지를 1-2 과정을 다시 수행합니다.
4. 즉, 정렬 1회전을 수행할ㄷ 때마다 정렬에서 제외되는 원소들이 쌓이고, 이것들이 정렬된 상태를 나타냅니다. 

• 버블 정렬의 복잡도

정렬해야할 원소가 n개라고 가정하면, 1회전에서 n번의 비교를 하고, 2회전에서 가장 마지막 원소를 제외하여 n-1번 비교를 하고, 마지막에는 1번의 비교만을 하게 됩니다. 따라서 버블 정렬의 시간 복잡도는 O(n^2)입니다. 

공간 복잡도는 다른 정렬 알고리즘과 마찬가지로 in-place 방식이기 때문에 O(n)입니다. 

• 버블 로직 Pyhton3 구현 코드 

def bubble_sort(q,n):
		#length가 4라면
    #바깥 루프는 3번 돌아야 하므로
    #range()는 0, 1, 2까지 즉 range(3)이 되야 하므로
    #range(list_length-1)이 되어야 한다.
    for i in range(n-1):
				#안쪽 루프는 1번당 3-> 2-> 1
        #즉 range(4 - 0 - 1) ->
        #range(4 - 1 - 1) ->
        #range(4 - 2 - 1)
        #range(list_leng - i - 1)
        for j in range(n-i-1):
						# 두 값을 비교하여 큰 값을 오른쪽에 위치시킴 
            if q[j] > q[j+1]:
                q[j], q[j+1] = q[j+1], q[j]

---

이번 글에서는 정렬 알고리즘과 그 중 삽입 정렬과 버블 정렬에 대해 설명하였습니다.

다음 글에서는 합병 정렬과 퀵 정렬에 대해 설명하겠습니다.

감사합니다 :)

 

---

References

• gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html