[12일차] python 정렬 알고리즘(Sorting algorithm)

python 정렬 알고리즘에 대해서 정리한다.

※ 정렬 알고리즘

- 정렬은 고전적인 문제 풀이법이자 알고리즘의 기초이다.

- python에서는 sorted()라는 정렬 알고리즘이 제공되지만 알아둔다면

다른 지원되지 않는 언어에서 사용이 가능하고 또한 sorted() 함수가 어떻게

동작하는지 알아갈수 있다.

- 정렬에는 선택정렬, 거품정렬, 합병정렬 등이 있는데 이 3가지 정렬이 가장 대표된다고 볼수 있다.

- 여러가지 정렬 알고리즘에 대해서 알아보고 싶다면 구글에서 sorting algorithm 이라고

검색해서 wikipedia를 들어가보면 표로 볼수있다.

( wikipedia에 보면 저번에 말했던 빅-오 표기법으로 최상, 평균, 최악의 경우에 정렬들의 성능이 나와있다 )

---

오늘은 선택정렬(selection sort)에 대해서 정리한다.

- 참고로 선택 정렬은 빅-오 표기법으로 Best, Average, Worst가 모두 n^2으로 나와있다

- 선택정렬은 [ 1, 4, 6, 3, 2, 8, 10, 9] 같은 수열이 있다면 가장 앞에 원소와 비교해서 가장 작은수를 찾아

제일 앞쪽으로 땡겨서 위치를 정렬해준다.

- python에서 선택정렬을 만들어보는데 여기서는 최소값을 가지고 오는 함수인 min()을 사용했다.

아래에는 선택정렬을 재귀함수, 꼬리재귀함수, 루프문 순서로 하나씩 작성해 봤다.

selection_sort.py