정렬 알고리즘

Bubble Sort에 이어서 선택정렬과 삽입정렬도 마스터해보자. range에 숫자 넣는게 헷갈리는 거만 빼면 상대적으론 쉬운 난이도.

Selection Sort(선택정렬)

• 배열을 순회하면서 i번째 순회에서 숫자를 골라 배열의 i번째 자리에 있는 숫자와 교체하는 방식으로 정렬한다.
• 맨 앞부터 정해진 위치에, 정렬될 원소를 선택하기 때문에 붙여진 이름인 듯

정수 배열 오름차순 정렬하기로 보는 Selection Sort 구현

• 배열의 길이 n, 인덱스를 i라고 할 때, n-1번 돌면서 i번째 돌 때는 i번째 요소부터 순회하며 가장 작은 수를 골라 i번째 요소와 바꾼다.

코드로 구현하기

1
2
3
4
5
6
7
8

def selection_sort(arr)
    for i in range(len(arr)-1):
        lowest = i
        for j in range(i+1, len(arr)):
            if arr[lowest] > arr[j]:
	        lowest = j
        arr[lowest], arr[j] = a[j], a[lowest]
    return arr

• 0부터 배열의 길이 n보다 한 번 적게 돌아가는 for문 안에서, 현재 돌아가는 인덱스 값을 lowest라는 변수에 담은 후 두번째 for문을 돌린다.
• 두번째 for문에서는 j가 하나씩 증가하며 돌아가는데, 이 j를 인덱스값으로 하는 요소가 i, 즉 lowest를 인덱스값으로 하는 요소보다 작으면 lowest 값에 j를 할당한다. 즉 lowest는 항상 순회하면서 가장 작은 값의 인덱스다.
• 두번째 for문이 끝나고 나면 lowest를 인덱스로 갖는 요소와 i를 인덱스로 갖는 값을 서로 바꾼다.
• 앞에서부터 i번째 요소까지는 이미 작업이 수행되어 정렬되었으므로 두번째 for문은 i+1부터 순회하게끔 range를 설정한다.

Selection Sort의 시간복잡도

• 반복문이 두개 중첩되어 있으므로 bubble sort와 같이 O(n²)의 시간복잡도를 갖는다.
• 정확하게는 n*(n-1)/2의 복잡도를 갖는다고 한다.

Insertion Sort (삽입 정렬)

• 앞에서부터 배열을 순회하면서, 순회 중인 인덱스 값의 요소와 바로 앞 요소를 비교하며 정렬하는 정렬
• 그 앞의 요소와 비교하는 조건을 만족하면 그 앞은 이미 정렬된 것과 마찬가지이므로 작업을 멈추고 다음 인덱스로 넘어간다.

정수 배열 오름차순 정렬하기로 보는 Insertion Sort 구현

• 배열의 길이 n, 인덱스를 i라고 할 때, n-1번 두 번째 for문을 돌린다.
• 두 번째 for문은 i+1번째 요소와 i번째 요소를 비교하며, 더 작은 숫자가 앞에 있다는 조건을 충족하면 두번째 for문을 빠져나가 i값을 증가시킨 첫번째 for문으로 돌아간다.

코드로 구현하기

1
2
3
4
5
6
7
8

def insertion_sort(arr):
    for i in range(len(arr)-1):
	for j in range(i+1, 0, -1):
	    if arr[j] < arr[j-1]:
		arr[j], arr[j-1] = arr[j-1], arr[j]
	    else:
		break
    return arr

• 첫번째 for문은 데이터의 길이보다 한 번 적게 반복문이 실행된다.
• 두번째 for문은 i+1의 인덱스값을 갖는 수부터 그 전의 요소와 비교하여 자신보다 작은 값이 나올 때까지 교체한다.
• 이미 작은 값을 앞에서부터 넣어주었기 때문에 자신보다 작은 값을 만나면 그 앞은 정렬되어있다고 보고 두번째 for문을 빠져나간다.

Insertion Sort의 시간복잡도

• 반복문이 두개 중첩되어 있으므로 bubble sort와 같이 O(n²)의 시간복잡도를 갖지만, 완전정렬된 최선의 경우 O(n)의 시간복잡도를 갖는다.

느낀 점

• range 안에 들어가는 숫자가 헷갈렸는데 일단 정렬의 모든 바깥 for문은 데이터의 전체 길이보다 1번 적은 턴을 돈다는 것을 잘 기억해야겠다.
• 거품정렬과 삽입정렬은 break가 있기 때문에 최선의 경우 시간복잡도가 O(n)까지 된다는 것이 인상깊다.

참고자료

• 패스트캠퍼스 코딩+알고리즘 온라인 완주반