[알고리즘] 정렬 알고리즘

정렬 알고리즘에 대해서 공부하기 전에 시간 복잡도에 대해서 알고 있어야 한다. 

 

 

시간복잡도

문제를 풀때(c/c++)기준 반복문과 기법을 생각하기 이전에 시간제한을 보고 접근하는게 PS의 가장 기본이다. 

PS를 할때 제한시간이 1초당 1억번 연산을 한다고 한다.

예시로 100만번 입력이 들어갈때 시간이 1초라면 기법은 최대 nlogn을 넘어서는 안된다.

 

1. 선택정렬

선택 정렬(Selection Sort)은 정렬되지 않은 데이터들 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 정렬 알고리즘이다. 선택 정렬은 다음과 같은 특징을 갖는다.

 

시간복잡도는 O(n^2)이다.

 

 

2. 삽입 정렬(Insertion Sort)

새로운 원소를 이전까지 정렬된 원소 사이에 올바르게 삽입시키는 방식으로 동작한다.

단순하지만 비효율적인 정렬 방법 중 하나이다.데이터의 배치에 따라 시간 복잡도가 달라진다.

 

최선의 경우 O(N), 평균과 최악의 경우 O(N^2)의 시간 복잡도를 갖는다.

 

 

3. 버블 정렬(Bubble Sort)

 

1. 인접한 두 원소를 비교하여 큰 원소를 배열의 끝으로 보내는 과정을 N-1번 반복한다.

 

2. 선택 정렬(Selection Sort)과 유사한 알고리즘으로, 서로 인접한 두 원소의 대소를 비교하고 교환하는 과정을 통해 정렬한다.

 

3. 시간복잡도는 o(n^2)으로, 배열의 크기가 커질수록 비교 및 교환 횟수가 급격히 증가하여 느리게 동작한다.(일일이 다 비교야하는 점)

 

 

4. 합병 정렬(Merge Sort)

1. 하나의 배열을 두 개의 균등한 크기로 분할하고, 분할된 배열을 각각 정렬한 후 다시 합쳐 정렬을 완성한다.

2. 평균, 최악의 경우 모두 O(NlogN)의 시간 복잡도를 가진다.

 

3.퀵 정렬과 달리 데이터 분포에 영향을 덜 받는다는 장점이 있다.다만 배열을 복사하는 과정에서 추가적인 메모리 공간이 필요하다는 단점이 있다.

 

5. 퀵 정렬(Quick Sort)

 

1. 피벗을 설정하여 이를 올바른 위치로 이동시킨 뒤, 나머지 원소들을 두 개의 부분 리스트로 분할하여 재귀적으로 정렬한다.

 

2. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

 

3. 평균적으로 매우 빠른 수행 속도를 자랑하며, 실제로도 많이 사용되는 알고리즘이다. 그러나 최악의 경우 시간 복잡도가 O(n^2)가 될 수 있다는 단점이 있다.