[알고리즘] 정렬 알고리즘(1) - 선택 정렬, 삽입 정렬

본 포스팅에서는 정렬 알고리즘에 대한 정리 내용을 담고있습니다.

(본 알고리즘 포스팅은 유튜브 '이코테 2021 강의'를 참고하여 작성하였습니다.)

 

 

https://www.youtube.com/@dongbinna

동빈나

 

 

---

 

정렬 이란?

정렬(sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 의미함.

 

 

① 선택 정렬

- 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해

맨 앞에 있는 데이터와 바꾸는 것을 반복하는 정렬

 

위와 같은 예시의 데이터가 있다고 가정.

 

 

 

처리되지 않은 데이터 중 가장 작은 데이터가 '0'이기 때문에

이 '0'을 선택해 가장 앞의 '7'과 바꾼다. 

 

 

 

그럼 위처럼 0은 이미 처리가 된 상태가 되는 것이고,

남은 데이터들 중 다시한번 가장 작은 데이터인 '1'을 선택해, 

가장 앞의 '5'와 바꾸는 작업을 반복한다. 

 

 

이 작업을 계속해서 반복해주면 아래와 같이 정렬이 완료된다.

 

 

이런 선택 정렬의 알고리즘은

이중 반복문을 사용해 파이썬에서 구현할 수 있다. 

 

arr 라는 변수에 위에서 본 데이터와 같은 값을 가진 리스트를 넣어준다.

i 라는 변수에는 가장 작은 원소의 인덱스를 반복해서 담아줄 것이고,

j가 들어있는 반복문에서 선형탐색을 실행하도록 한다. 

반복문을 돌면서 i 위치의 원소보다 j 위치의 원소의 값이 더 작다면,

가장 작은 원소의 인덱스는 i가 아닌 j로 업데이트 되게 된다. 

 

j가 들어있는 반복문 부분에서 반복문을 다 돌고 나면,

i위치의 원소(가장 앞쪽에 놓인 원소)와 가장 작은 값의 원소를 서로 스와프 해준다. 

 

---

 

② 삽입 정렬

- 처리되지 않은 데이터를 하나씩 골라서 적절한 위치에 삽입한다. 

- 선택정렬에 비해서 구현 난이도는 높지만, 일반적으로 더 효율적으로 동작함

 

 위에서 보았던 예시를 그대로해서 삽입 정렬의 동작 과정을 살펴보면 다음과 같다. 

첫 번째 데이터인 '7'은 그 자체로 이미 정렬이 되어 있다고 판단하고,

두 번째 데이터인 '5'가 '7'의 왼쪽 / 오른쪽 두 경우중 어떤 위치로 들어갈지 판단한다. 

즉, 우리가 오름차순으로 데이터를 정렬하려고 한다면 5가 7의 왼쪽으로 들어가도록 한다. 

 

 

이어서 그 다음 데이터인 '9'가 어떤 위치로 들어갈지 판단한다. 

이 과정을 계속해서 반복하면 전체 데이터에 대한 정렬이 완료된다.

 

 

이런 삽입 정렬 알고리즘 역시

파이썬에서 이중 반복문을 활용해 구현이 가능하다. 

 

위에서 언급한대로 삽입 정렬은 

첫 데이터는 이미 정렬이 되어있다고 가정하기 때문에

i가 있는 반복문을 보면 range가 index 0이 아닌 1 부터 시작하는 것을 알 수 있다. 

j가 있는 반복문을 보면 j와 j-1을 비교하여 (왼쪽 값과 비교)

왼쪽의 값이 더 크다면 서로 스와핑 해준다.