[Algorithm] 선택 정렬, 버블 정렬, 삽입 정렬 알고리즘

선택 정렬

Idea

선택 정렬은 주어진 값들 중 최소값을 맨 앞으로 땡겨와서 정렬하는 방법입니다.

170cm, 180cm, 150cm, 160cm

예를 들어 4명의 사람을 키 순서로 정렬하고자 할 때, 선택 정렬의 방식을 따른다면, 우선 150cm을 맨 앞에 세우고 나머지 3명의 키를 비교합니다.

 150cm[정렬 완료] || 170cm, 180cm, 160cm

3명 중에서는 160cm가 가장 작으므로 앞쪽으로 땡겨오고, 먼저 앞으로 간 150cm 뒤에 위치하도록 합니다.

 150cm, 160cm[정렬 완료] || 170cm, 180cm

이를 반복하면 최종적으로 키 순서대로 사람들이 정렬될 것입니다.

Code

이를 코드로 구현하면 다음과 같습니다.

def selection_sort(people):
	length = lem(people)
	for i in range(0, length-1):
		min_index = i
		for j in range(i, length-1):
			if peopel[j] < people[min_index]:
				min_index = j
		people[i], people[min_index] = people[min_index], people[i]   # swapping

Time complexity

위 코드에서 알 수 있듯이 2개의 loop를 거치므로 총 O(N^2)의 시간 복잡도를 가집니다.

---

버블 정렬

Idea

버블 정렬은 인접한 두 원소의 값을 비교하여, 큰 값을 오른쪽으로 하나씩 이동시키는 방법입니다. 따라서 loop 한 번을 거치면 가장 큰 값이 오른쪽에 정렬되게 됩니다.

170cm, 180cm, 150cm, 160cm

아까와 같이 키 순서대로 정렬시킬 때 버블 정렬 방법을 사용하면 우선 맨 앞의 2명을 비교합니다. 이 경우 180cm가 더 크므로 그대로 오른쪽에 위치하게 됩니다.

170cm, 150cm, 180cm, 160cm

다음으로, 180cm와 150cm를 비교하면 180cm가 더 크므로 오른쪽으로 이동합니다.

170cm, 150cm, 160cm, || 180cm [정렬 완료]

마지막으로 180cm와 160cm를 비교하면 180cm가 더 크므로 오른쪽으로 이동합니다. 이렇게 가장 큰 180cm가 가장 오른쪽에 위치하게 되었습니다.

이와 같이 반복하게 되면 다음으로는 170cm가 오른쪽 칸으로 이동하게 될 것이고 (180cm 앞) 나머지도 결국 오른쪽 칸으로 모두 정렬된 채로 이동하게 될 것입니다.

Code

def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1):
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

Time complexity

위 코드에서 알 수 있듯이 2번의 loop를 거치므로 버블 정렬은 총 O(N^2)의 시간 복잡도를 가지게 됩니다.

---

삽입 정렬

Idea

삽입 정렬은 정렬 범위를 1칸씩 늘려가면서 새롭게 정렬 범위에 들어온 값을 알맞은 자리에 삽입시키는 정렬 알고리즘입니다.

170cm, 180cm, 150cm, 160cm

우선 앞에서 2개만 정렬 범위에 포함시킨다고 생각하면, 이미 정렬된 상태입니다. 여기서 정렬 범위를 1칸 늘려 150cm까지 포함시킨다면, 150cm은 맨 앞으로 ‘삽입’되므로 아래와 같이 정렬됩니다.

150cm, 170cm, 180cm, [정렬 완료] || 160cm

다시 정렬 범위를 1칸 늘려 160cm까지 포함시키면 정렬이 완료됩니다.

150cm, 160cm ,170cm, 180cm

Code

def insertion_sort(arr):
    for end in range(1, len(arr)):
        for i in range(end, 0, -1):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]

2번째 loop가 방금 범위에 포함된 값을 이미 정렬된 리스트에서의 자리를 찾아가는 과정입니다.

Time complexity

위 코드에서 2개의 loop가 필요하므로 삽입 정렬은 총 O(N^2)의 시간 복잡도를 가지는 정렬 알고리즘입니다.