[공주는 코딩하고 싶어] 7회차. 정렬

정렬

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

 

정렬 알고리즘으로 데이터를 정렬하면 이진탐색이 가능하다.

 

컴퓨터는 어떻게 정렬을 수행할지에 대한 과정을 구체적으로 명시해줘야 한다.

내림차순 정렬은 오름차순 정렬 수행 알고리즘에서 크기 비교문을 반대로 수행하면 된다.

파이썬에서는 특정 리스트의 원소를 뒤집는 메서드를 제공하기 때문에 리스트를 오름차순으로 정렬한 후 뒤집기 메소드를 적용하면 내림차순 정렬을 얻을 수 있다. (이때, 뒤집는 연산은 O(N) 복잡도로 간단하게 수행 가능하다.)

 

선택정렬

- 가장 원시적인 방법

- 가장 작은 데이터를 찾아서 맨 앞 데이터와 바꾸고 그 다음 작은 데이터를 찾아서 두 번째 데이터아 바꾸는 과정을 반복한다.

- 즉, 데이터가 N개일 때 데이터를 앞으로 보내는 과정을 N-1번 하면 정렬이 완료된다.

- 시간 복잡도 : O(N^2)

 

삽입 정렬

- 특정한 데이터를 적절한 위치에 삽입

- 데이터가 거의 정렬되어 있을 때 효율적이다. -> O(N)

- 시간 복잡도 : O(N^2)

 

퀵 정렬

- 가장 많이 사용되는 알고리즘

- 기준 = pivot을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누면서 정렬하는 방식

- 퀵정렬을 수행하기 전에 pivot을 먼저 설정해줘야 한다.

- 데이터가 무작위일 때 효율적이다. (이미 데이터가 정렬되어 있는 경우에는 매우 느림)

- 시간 복잡도 : O(N logN) (but 최악의 경우에는 O(N^2)

 

계수 정렬

- 모든 범위를 담을 수 있는 크기의 리스트를 선언해서 리스트에 정렬에 대한 정보를 담는다

- 데이터를 앞에서부터 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시키고 추후에 리스트의 각 인덱스를 확인하면서 데이터 중 최댓값의 크기만큼 반복을 수행한다.

- 비교 기반의 정렬 알고리즘이 아니다.

- 시간 복잡도 : O(N+K)   (K는 데이터 중 최대 값의 크기)

- 공간 복잡도 : O(N+K)

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

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

- 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용 가능