정렬 알고리즘 (1) : 선택 정렬

이전 글에서 알고리즘이 무엇인지, 왜 배워야 하는지에 대한 이야기를 간단히 나눴습니다.

이번 글부터는 알고리즘의 기본, 정렬 알고리즘에 대해 공부해보겠습니다.

정렬 알고리즘이 무엇인지 그리고 정렬 알고리즘의 종류에는 무엇이 있는지 이야기하고, 이번 글에서는 정렬 알고리즘 중 선택 정렬에 대해 설명하겠습니다. 

---

정렬 알고리즘 Sorting Algorithm

• 정렬 알고리즘의 개념

n개의 데이터가 입력(input)으로 주어졌을 때, 이를 사용자가 지정한 기준(내림차순, 오름차순 등)에 맞게 데이터를 정렬하여 출력(output)하는 알고리즘을 말합니다.

정렬 알고리즘은 다른 알고리즘을 최적화하는데 중요한, 아주 기본적인 알고리즘입니다. 따라서 다양한 정렬 알고리즘이 발명되었고, 계속해서 더 효율적인 정렬 알고리즘이 연구되고 있습니다.

 

• 정렬 알고리즘의 종류 

그 종류로는 선택 정렬, 삽입 정렬, 버블 정렬, 합병 정렬, 퀵 정렬 등이 있습니다. 

 

---

선택 정렬 Selection Sort

• 선택 정렬의 개념 

선택 정렬은 배열에서 값이 들어갈 적절한 위치를 찾아 정렬하는 알고리즘 으로 배열에서 특정 위치에 어떤 원소를 넣을지 선택하는 것입니다. 

즉, 오름차순 선택 정렬이라고 가정하면 배열의 가장 첫번째 자리에 가장 작은 원소, 두번째 자리에 정렬되지 않은 원소들 중 가장 작은 원소, ... 이런 방식으로 정렬이 진행되는 것입니다. 

 

• 선택 정렬 기본 로직

정렬되는 기준이 오름차순일 경우 최소 선택 정렬을, 내림차순일 경우 최대 선택 정렬을 하게 됩니다. 

1. 정렬되지 않은 인덱스를 배열의 맨 앞(가장 왼쪽)에서부터 오른쪽 방향으로 순회하며 배열에서 가장 작은 값을 찾는다.
2. 발견한 가장 작은 값을 현재 원소의 위치와 바꾼다.
3. 다음 인덱스로 넘어가서 위 1, 2 과정을 반복한다.
4. 현재 인덱스가 배열의 맨 끝(가장 오른쪽)에 있는 인덱스에 도달할 때까지 반복 수행한다.

• 선택 정렬 복잡도

처음 정렬되어 있지 않은 배열의 모든 값을 모든 다른 값들과 비교하여 교체를 수행하기 때문에 시간 복잡도는 O(n^2)입니다. 

선택 정렬은 제자리(in-place) 정렬 알고리즘 중 하나입니다. 따라서 배열에 들어있는 원소의 개수만큼만 필요하기 때문에 공간 복잡도는 O(n)을 나타냅니다. 

*제자리 정렬 알고리즘이란 정렬하고자 하는 배열 이외에 추가적인 메모리를 요구하지 않는 정렬 방법을 의미합니다. 

 

• 선택 정렬 예제 

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

 

---

선택 정렬 Python3 구현 코드

def selection_sort(q,n):
    for i in range(0, n-1):
        # 리스트의 모든 원소 n-1개에 대해 (마지막 원소 제외)
        min = i
        for j in range(i+1, n):
            # 해당 원소 다음 원소부터 리스트 끝까지 해당 원소와 비교 
            if q[j] < q[min]:
                # min이 해당 원소를 임시로 저장해둔 변수인데 해당 원소가 리스트 순회하면서 자기보다 작은 원소를 찾으면
                min = j
                # 그 원소가 min이 된다. 
        q[i], q[min] = q[min], q[i]
        # 해당 원소와 가장 작았던 원소 min 의 위치를 swap!
        # 이 과정을 n-1번 수행하면 오름차순으로 정렬됨.
        
# 원소 개수 입력 받기 
n = int(input())
# 배열의 원소 입력받기 
q = list(map(int, input().split()))

# 위에서 구현한 함수 호출
selection_sort(q,n)

# 정렬 함수 결과 출력 
for i in q:
    print(i, end=' ')

---

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

다음 글에서는 삽입 정렬에 대해 설명하겠습니다.

감사합니다. 

 

---

References

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