정렬 알고리즘

정렬 알고리즘 종류

요소들을 특정 순서대로 재배치하는 것을 정렬이라고 하며 

이런 정렬을 하는 알고리즘의 종류에는 대표적으로 버블, 삽입, 선택, 퀵, 병합, 힙 정렬이 있습니다.

 

알고리즘 별 시간 복잡도를 먼저 말씀드리자면 다음과 같습니다. 

버블, 삽입, 선택: O(N^2)

퀵, 병합, 힙: O(N logN)

 

버블 정렬

서로 인접해 있는 요소 간 대소 비교를 통해 정렬하는 알고리즘입니다.

추가적인 메모리 공간이 필요하지 않다는 특징이 있으며

쉽게 구현할 수 있지만 비효율적인 알고리즘입니다.

 

인접한 원소를 교환하는 모습이 마치

물 속의 거품과 비슷하다고하여 버블 정렬이라고 부른다고 합니다.

 

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

 

버블 정렬에 로직에 대한 자세한 설명 및 코드는 아래의 링크에 있습니다.

버블 정렬(Bubble Sort)

 

삽입 정렬

정렬을 진행할 원소의 index(a)보다 작은 곳(0~a-1)에 있는 원소들을 탐색하고

알맞은 위치에 삽입하여 정렬하는 알고리즘입니다.

구현이 간단하다는 특징이 있습니다.

 

오름차순 정렬 기준

1~N-1번째 인덱스를 순차적으로 key로 두고

key-1 ~ 0의 인덱스를 감소순회하면서

만약 arr[현재의 값] > key 라면, arr[현재의 값+1] = arr[현재의 값]을 넣어줍니다.

그렇지 않다면, 순회를 종료합니다.

순회가 끝나고 난 후, arr[마지막 위치 + 1] = key 값으로 갱신합니다.

 

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

 

삽입 정렬에 로직에 대한 자세한 설명 및 코드는 아래의 링크에 있습니다.

삽입 정렬(Insertion Sort)

 

선택 정렬

요소들 중에서 최대/최소값을 찾아 정렬하는 알고리즘입니다.

최대값 선택 시 내림차순 정렬을 진행합니다.(최솟값 선택 시 오름차순 정렬)

 

오름차순 정렬을 기준으로 보자면

먼저 0~N-1 요소들 중에서 가장 작은 값을 찾고 0번째 인덱스와 교환해줍니다.

 

그다음 정렬된 0번째를 제외한

1~N-1 요소 중에서 가장 작은 값을 찾고 1번째 인덱스와 교환해줍니다.

 

이렇게 총 N-2번(마지막 인덱스 탐색 X) 반복하면 정렬이 완료됩니다.

 

추가 메모리 공간이 필요하지 않는 특징이 있습니다.

 

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

 

선택 정렬에 로직에 대한 자세한 설명 및 코드는 아래의 링크에 있습니다.

선택 정렬(Selection Sort)

 

 

퀵 정렬

피벗을 기준으로 큰 값과 작은 값을 나누어 정렬하는 방식의 알고리즘입니다.

분할 정복 방법을 사용하며 대용량 데이터를 정렬할 때 유리합니다.

 

시간 복잡도: O(N logN)

 

퀵 정렬에 로직에 대한 자세한 설명 및 코드는 아래의 링크에 있습니다.

 

퀵 정렬(Quick Sort)

 

병합 정렬

배열을 반으로 나눈 후, 각각을 정렬하고 합쳐서 정렬된 리스트를 생성하는 방식입니다.

분할 정복과 재귀 알고리즘을 사용합니다.

원소가 하나만 남을 때까지 이분할을 진행합니다.

추가적인 메모리 공간이 필요합니다.

 

시간 복잡도: O(N logN)

 

힙 정렬

힙 자료구조인 완전이진트리를 기반으로 정렬하는 방식의 알고리즘입니다.
오름차순 정렬은 최소 힙, 내림차순 정렬은 최대 힙을 사용합니다.

 

최소힙의 경우, 부모 노드가 자식 노드보다 항상 작은 값을 가집니다. 
반대로 최대힙의 경우, 부모 노드가 자식 노드보다 항상 큰 값을 가집니다. 

완전이진트리이기 때문에, 중앙 값에 가까운 근사치로 빠르게 탐색할 수 있습니다. 
이진탐색트리와 달리 중복된 값을 허용한다는 특징을 가집니다. 

우선순위 큐, 다익스트라, 프림 알고리즘에 활용됩니다.

 

시간 복잡도: O(N logN)