[#4] 정렬 (chapter6)

참고 출처

: 이것이 코딩테스트다 with 파이썬

 

---

1. 기준에 따라 데이터를 정렬

정렬이란?

데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미한다.

면접에서 단골문제로 자주 등장한다.

리스트를 뒤집는 연산은 O(N)의 복잡도로 간단히 수행할 수 있다.

정렬은 이진탐색의 전처리과정이다.

정렬 종류 : 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬

---

(1) 선택 정렬

: 매번 가장 작은 것을 선택한다는 의미.

가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면,

전체 데이터의 정렬이 이루어진다.

 

스와프?

특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업이다.

선택정렬의 시간복잡도는 O(N^2) #2중 반복문이 사용되었기 때문

 

---

(2) 삽입 정렬

: 특정한 데이터를 적절한 위치에 삽입한다.

(적절한 위치에 들어가기 전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정함)

삽입 정렬은 두 번째 데이터부터 시작한다. 

첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문에

 

선택 정렬보다 실행 시간 측면에서 더 효율적이다.

데이터가 거의 정렬 되어 있을 때 훨씬 효율적이다. (필요할 때만 위치를 바꾸기에)

정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다.

 

---

(3) 퀵 정렬

기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식이다.

피벗이 사용된다.

피벗은 큰 숫자와 작은 숫자를 교환할 때 교환하기 위한 기준을 의미함.

 

가장 대표적인 방식이 호어 분할 방식

>> 리스트 첫 번째 데이터를 피벗으로 설정한다.

 

퀵 정렬은 재귀 함수 형태로 작성했을 때 구현이 매우 간결해진다.

퀵 정렬이 끝나는 조건은 현재 리스트의 데이터 개수가 1개인 경우이다.

 

---

(4) 계수 정렬

: 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.

데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을때만 사용할 수 있다.

(1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다)

먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다.

처음엔 리스트의 모든 데이터가 0이 되도록 초기화하고,

그 다음 데이터를 하나씩 확인해가면서 동일한 인덱스의 데이터를 1씩 증가시키면 됌

 

계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 떄 적합하다.

즉, 데이터 크기가 한정되어 있고 데이터의 크기가 많이 중복되어 있을수록 유리하다.

 

---

(5) 파이썬의 정렬 라이브러리

파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다.

sorted는 퀵 정렬보단 느리지만 최악의 경우에도 O(NlogN)을 보장하는 병합 정렬이다.

sorted(리스트명)

 

sort()를 이용하면, 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 바뀌어버린다.

리스트명.sort()

 

즉 sorted는 출력값만 바뀌게 하는거고, 리스트의 정렬 상태는 똑같다

sort는 리스트의 정렬상태를 아예 바꿔버리는 것을 의미함.

 

데이터의 범위가 한정되어 있으며 더 빠르게 동작해야할 경우에만 계수 정렬을 사용하고,

별도의 요구 없이 단순정렬을 해야하면 파이썬 정렬 라이브러리를 적극 사용!

 

완전 빠른 정렬이 필요할 경우엔 계수 정렬!