<PART 2> 정렬

정렬:데이터를 특정한 기준에 따라서 순서대로 나열하는 것

데이터를 가공할 때 오름차순, 내림차순 등으로 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램 작성할 때 가장 많이 사용되는 알고리즘 중 하나입니다. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해집니다.
정렬의 종류가 많지만 선택정렬, 삽입정렬, 퀵정렬, 계수정렬만 적겠습니다.

- 선택 정렬
데이터가 무작위로 있을 때, 가장 작은 데이터를 맨 왼쪽 데이터와 자리를 교환합니다. 그다음은 맨 왼쪽 데이터를 제외한 숫자 중에서 가장 작은 값과 그 다음 왼쪽의 값을 서로 바꿉니다. 이 과정을 반복합니다.

위는 저의 방법, 아래는 책의 방법입니다.
저는 맨왼쪽이 최솟값이면 그대로 두고 아니라면 temp를 두어서 바꿔주었습니다.
책은 차례대로 비교해서 작은값의 인덱스를 구하고 한꺼번에 바꿔주었습니다.

파이썬은 다른 프로그래밍언어와 달리 temp라는 임시저장용변수없이 동시에 두 변수의 위치를 바꿔줄 수 있습니다. 이를 Swap라고 하며 a,b = b,a처럼 선언해줄 수 있습니다.

- 삽입정렬
선택정렬은 알고리즘 문제를 풀 때 느린편입니다. 삽입정렬은 구현난이도가 높지만 대부분의 데이터가 정렬되어 있을 때 빠릅니다. 가장 왼쪽에 있는 숫자부터 그 다음 수를 비교해서 오름차순으로 크기에 맞게 삽입하는 과정입니다.

뒤에서 부터 인덱스를 감소시키면서 오름차순이 되도록 위치를 바꿔나갑니다.

- 퀵 정렬
퀵 정렬은 지금까지 배운 정렬 알고리즘 중에서 가장 많이 사용되는 알고리즘입니다. 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면서 정렬하는 방법입니다. 

이처럼 피벗을 정하고 왼쪽은 피벗보다 작은값, 오른쪽은 큰값이 되도록 위치를 바꿉니다. 그 이후에 피벗을 제외하고 나머지 array에서 맨왼쪽데이터를 다시 피벗으로 정하고 퀵정렬합니다.

- 계수 정렬
특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘입니다. 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있습니다. 계수라는 이름답게 가장 작은 데이터와 가장 큰 데이터가 담길 수 있도록 빈 리스트를 만듭니다. 그리고 나서 리스트에 담긴 원소들에 해당하는 값의 해당인덱스를 +1씩 해줍니다.

모든 원소를 담을 수 있는 리스트를 만들어 줍니다. 그리고 각 데이터에 해당하는 인덱스의 값을 증가시키면 됩니다. 그런 다음에 한 원소가 중복되어 있는 것까지 출력시켜 줍니다.

- 정렬알고리즘 시간복잡도

정렬알고리즘	평균시간복잡도	공간복잡도	특징
선택 정렬	O(N^2)	O(N)	아이디어가 매우 간단
삽입 정렬	O(N^2)	O(N)	데이터가 거의 정렬되어 있을 때는 가장 빠름
퀵 정렬	O(NlogN)	O(N)	대부분의 경우에 가장 적합, 충분히 빠름
계수 정렬	O(N+K)	O(N+K)	데이터의 크기가 한정되어 있는 경우에만 사용이 가능하지만 매우 빠르게 동작합니다.

 

- 파이썬의 기본 정렬 라이브러리
sorted()함수를 제공합니다. 이는 퀵정렬과 동작방식이 비슷한 병합정렬을 기반으로 만들어졌는데 퀵 정렬보단 느리지만 최악의 경우에도 시간 복잡도가 O(NlogN)를 보장하는 특징이 있습니다.

1. sorted
result = sorted(array)
-> 반환값이 존재하고 원래의 리스트는 변함이 없습니다.
2. sort
array.sort
-> 별도의 반환값이 존재하지 않고 바로 리스트를 정렬시킵니다.
3. sorted(key=함수명)
result = sorted(array, key=lambda x:x[1]), sort도 가능
->key속성을 주어서 함수를 넣고 그 값에 해당하는 대로 오름차순 정렬시킵니다. 튜플형태로 값이 주어지고 그 중의 1개의 값으로 정렬시켜야 할 때 자주 사용됩니다.