[Algorithm] 선택 정렬(Selection Sort) .02

이번에 알아볼 알고리즘은 선택 정렬(Selection Sort) 입니다.

해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘입니다.

쉽게 말해 모든 원소를 훑어 제일 작은(큰) 원소부터 차곡차곡 정렬하는 방식입니다.

 

키 순으로 줄 서!

🤔 과정 및 코드

해당 순서에 원소를 넣을 위치를 정해 놓고 조건에 맞는 원소를 선택하고 넣으며 정렬합니다.

 

📝 Python 예시 코드.

def Selection_Sort(arr):
    for i in range(0, len(arr)):
        index = i
        for j in range(i+1, len(arr)):
            if arr[index] > arr[j]:
                index = j
        temp = arr[i]
        arr[i] = arr[index]
        arr[index] = temp
    return arr

 

🕒 시간 복잡도.

버블정렬과 마찬가지고 반복문이 두 번 돌기 때문에 O(n^2) 시간복잡도를 가지고 있습니다.

데이터의 개수가 n개라고 했을 때,

• 첫 번째 회전에서의 비교횟수 : 1 ~ (n-1) => n-1

• 두 번째 회전에서의 비교횟수 : 2 ~ (n-1) => n-2

  ...

• (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

💾 공간 복잡도.

주어진 배열 안에서 교환을 통해, 정렬이 수행되므로 O(n) 입니다.

 

✋ 장점과 단점.

장점.

구현이 쉽고, 코드가 직관적이다.

배열 안에서 교환하는 방식으로 다른 메모리 공간을 필요로 하지 않는다. (제자리정렬 - in-place sorting)

 

단점.

최악,최선,평균 어느 상황에서나 O(n^2) 시간 복잡도를 가진다. (Bubble정렬보단 조금 빠름)

정렬 되어 있지 않은 원소가 정렬될 때 많은 자리 이동이 일어난다.

 

참조.

GimunLee/tech-refrigerator