알고리즘) 정렬 알고리즘

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

 

1. 선택 정렬

처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 비교하여 맨 앞의 데이터와 바꾸는 것

-> 가장 작은 데이터를 맨 앞으로 

이중 반복문으로 구현

시간복잡도는 O(N^2)

 

2. 삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입

-> 데이터를 하나씩 선택해 다른 데이터와 하나씩 비교하며 작으면 왼쪽 크면 오른쪽에 위치시킴

 

선택 정렬에 비해 구현 난이도는 높지만, 더 효율적

시간복잡도는 O(N^2)

현재 데이터가 정렬되어있을수록 시간복잡도는 O(N)에 가까워짐

 

3. 퀵 정렬

기준 데이터를 설정, 기준보다 큰 데이터와 작은 데이터의 위치를 변경

일반적으로 가장 많이 사용된다

병합 정렬과 함께 대부분 프로그래밍 언어의 정렬 라이브러리의 근간이 된다

기본적으로 첫 번째 데이터를 기준 데이터(pivot)로 설정

1) 피벗설정 

2) 왼쪽에서 부터 피벗보다 큰 값, 오른쪽에서 부터 피벗보다 작은 값을 찾아 서로 바꾼다

3) 2번의 왼쪽에서 큰 값과 오른쪽에서 작은 값의 위치가 서로 역전될 때 작은쪽의 데이터와 피벗의 위치를 바꾼다

-> 피벗이 가운데, 왼쪽엔 피벗보다 작은 수, 오른쪽엔 큰 수 로 분할 되게 된다

4) 1번에서 설정한 피벗을 제외한 왼쪽, 오른쪽의 배열에 각각 1-2-3번 수행 (재귀적)

시간복잡도는 평균적으로 O(NlogN),  최악의 경우 O(N^2) 

-> 이미 정렬되어있는 데이터의 경우 매번 선형 탐색을 해야하기 때문에 O(N^2)

-> 프로그래밍 언어의 표준 라이브러리는 O(NlogN)을 보장하는 형태로 수정되어있음

 

4. 계수정렬

특정한 조건에만 사용 가능하지만 매우 빠름

최악의 경우에 O(N+K)

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

 

1. 가장 작은 데이터부터 가장 큰 데이터까지의 범위를 인덱스로 생성하여 개수를 카운팅

2. 카운팅된 수 만큼 해당 인덱스를 생성

 

-> 연속된 데이터, 동일한 값을 데이터가 여러개 등장할 때 효과적으로 사용 가능

데이터 단위의 차이가 클수록 비효율적