[알고리즘] 정렬 | [1] 정렬, 선택 정렬 (Selection Sort) - Python

[알고리즘] 정렬 | [2] 삽입 정렬 (Insertion Sort) - Python

[알고리즘] 정렬 | [2] 삽입 정렬 (Insertion Sort) - Python

[알고리즘] 정렬 | [3] 퀵 정렬 (Quick Sort) - Python

 

[알고리즘] 정렬 | [3] 퀵 정렬 (Quick Sort) - Python

[알고리즘] 정렬 | [4] 계수 정렬 (Counting Sort) - Python

 

[알고리즘] 정렬 | [4] 계수 정렬 (Counting Sort) - Python

 

 

^ 다른 정렬들이 궁금하다면 ^

 

1. 정렬(Sorting)이란?

1) 정렬은 '특정한 기준에 따라서 데이터를 순서대로 나열하는 것'을 뜻한다. '오름차순', '내림차순'이 이에 해당한다.

2) 정렬 알고리즘은 단순히 데이터를 정렬하는 것을 넘어 '이진탐색(Binary Search)'을 가능하게 하는 전처리 단계와 같다.

 

이때, 이진탐색이란?

- 간단히 말하면 검색한 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘을 의미한다.

- 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고, 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다.

- 즉, 리스트의 중간 부분에서부터 찾는 원소가 있는지 확인하는 과정으로, 쉽게 말하면 up/down 게임과 동일한 개념이다.

 

 

- 정렬 알고리즘의 종류는 많지만, 코딩테스트에 많이 사용되는 정렬은 아래와 같으므로 이들만 정리할 것이다.

- 선택 정렬 / 삽입 정렬 / 퀵 정렬 / 계수정렬

 

 

2. 선택 정렬(Selection Sort)

1) 선택 정렬의 원리

- 데이터가 무작위로 있을 때에 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복하는 정렬

- 가장 원시적인 방법

- "늘 가장 작은 것을 선택한다"는 의미에서 선택 정렬 알고리즘이라고 부른다.

 

이해를 돕기 위한 애니메이션이 아래에 준비되어 있다.

 

출처: [위키백과] 선택정렬

그림과 무작위로 퍼져있던 데이터 중에서, 가장 작은 값을 가져와 순서대로 줄을 세우는 것이 선택정렬이라고 이해할 수 있다.

 

이제 코드를 통해 이해를 해볼 것이다.

 

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
	min_index = i # 최소값의 인덱스
    
    for j in range(i+1, len(array)):
    	if array[min_index] > array[j]:
        	min_index = j
    array[i], array[min_index] = array[min_index], array[i]
    
    
print(array)

#[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

위 코드를 하나하나 뜯어서 해석하면

 

악필이지만 어느정도 알아보실 수 있을 거라고 생각하며 🙄...

저처럼 아예 입문자이신 분들도 이해할 수 있도록 하나씩 뜯어서 설명하였습니다.

 

 

간단하게 요약하자면,

선택 정렬은 "첫 번째 값부터 마지막 값까지 하나하나 가장 작은 값을 앞으로 고정하는 것"이다.

 

Q1. 가장 작은 값부터 첫 번째 자리에 채우는 것이라고 했는데, 가장 작은 값을 어떻게 찾아요?

A1. 함수 설정하면 알아서 해줍니다...가 아니라, 자신의 위치(k) 바로 다음부터 하나씩 비교해가면서 작은 값이 존재하면 자신과 자신(k)와 위치를 바꾸는 것입니다.

 

코드 블럭이 아니라 가독성이 떨어지지만...

자신의 위치(k) 바로 다음인 (k+1)과 비교해보고 k가 더 크고 k+1이 더 작다? 그러면 k+1을 k라고 지정해서 위치를 바꿔버리고, 그 다음에 또 바꾸고... 또 바꾸고... 바꾸고... 바꾸고... 하다 보면 오름차순 정렬이 완성됩니다.

 

예) [9, 3, 1, 5]

>> [3, 9, 1, 5]

>>> [3, 1, 9, 5]

>>>> [3, 1, 5, 9]  # 제일 큰 수를 가장 뒤로 보냈다! 다시 앞으로 돌아가서

>>>>> [ 1, 3, 5, 9 ] # 오름차순 정렬 완성

 

이런 식으로 진행됩니다.

 

Q2. 자리 고정이 무슨 말인가요?

A2. 첫 번째 자리부터 고정해나가기 때문에, 내가 i 자리를 고정했다면 그 다음은 i+1 자리를 보면 됩니다.

초록색 형광펜 보이시나요?

---

출처: [위키백과] 선택정렬

글을 마치기에 앞서, 이제 이 애니메이션이 이해가 되시나요?

혹시 이해가 안 되시면 언제든 댓글 부탁드립니다!

같이 공부하며 성장해요 🥰

 

 

시간 복잡도가 궁금하다면?