[알고리즘]정렬

정렬은 알고리즘의 기초. 

정렬을 배우면서 문제 해결의 기초를 다질 수 있다.

모든 개발자가 알아야 하는 가장 기본적인 알고리즘!

sorted 나 .sort() 함수가 있어도 알아야 한다.

이걸 모른다면 개발자라고 말을 할 수 없을정도.(부끄러운 사실!)

 

정렬이란?

리스트의 원소들을 특정 순서로 정리하는 것

예)오름차순 정리, 내림차순 정리, 가나다 순으로 정리

 

선택정렬(Selection Sort)

:가장 먼저 생각나는 자연스러운 기본 알고리즘

각 위치에 어떤 값이 들어갈지 찾는다. 

리스트를 순서대로 보면서 원하는 값을 찾아낸다

 

1. [2 4 5 1 9]
2. 현재의 최솟값은 맨 앞의 요소인 2이다.
3. 2와 4를 비교했을때 2가 작으므로 현재의 최솟값은 2로 유지된다.
4. 현재 최솟값인 2와 5를 비교 했을때, 2가 작으므로 최솟값이 2로 유지된다.
5. 2와 1을 비교했을때 1이 작으므로 최솟값이 1로 바뀐다.
6. 1과 9를 비교했을때 1이 작으므로 최솟값이 1로 그대로 유지된다.
7. 1과 2의 위치를 바꿔준다 [1 4 5 2 9]
8. 4와 5를 비교했을때 4가 작으므로 최솟값이 4로 유지된다.
9. 4와 2를 비교했을때 2가 작으므로 최솟값이 2로 바뀐다.
10. 2와 9를 비교했을때 2가 작으므로 최솟값이 2로 유지된다.
11. 4와 2의 위치를 바꿔준다 [1 2 5 4 9]
12. 5와 4를 비교했을때 4가 작으므로 최솟값이 4로 바뀐다.
13. 4와 9를 비교했을때 4가 작으므로 최솟값이 4로 유지된다.
14. 5와 4의 위치를 바꿔준다 [1 2 4 5 9]
15. 5와 9를 비교했을때 5가 작으므로 그대로 둔다
16. [1 2 4 5 9]

 

정렬 종료!

삽입정렬(Insertion Sort)

:각 값이 어떤 위치에 들어갈지 찾는다.

 

1. [2 4 5 1 9]
2. 2와 4를 비교했을때, 2가 4보다 작으므로 그냥 둔다
3. 4와 5를 비교했을때, 4가 5보다 작으므로 그냥 둔다
4. 5와 1을 비교했을때, 5가 1보다 크므로 서로 자리를 바꾼다.
5. [2 4 1 5 9]
6. 4와 1을 비교했을때, 4가 1보다 크므로 서로 자리를 바꾼다.
7. [2 1 4 5 9]
8. 2와 1을 비교했을때, 2가 1보다 크므로 서로 자리를 바꾼다.
9. [1 2 4 5 9]
10. 5와 9를 비교했을때, 5가 9보다 작으므로 그냥 둔다

 

정렬 종료!

 

위의 두가지 정렬 외에 여러가지 정렬들이 있다.

(힙 정렬, 버블 정렬 등)

개발자를 위한 정렬 알고리즘

Sorting Algorithms Animations | Toptal®