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

1. 선택정렬

개념

가장 작은 것을 선택하여 맨 앞으로 보낸다.

구현하기 쉽다.

무조건 큰 경우대로, 무조건 작은 경우대로, 무조건 긴 경우대로, 무조건 짧은 경우대로 등 극단적으로 문제에 접근한다는 점에서 정렬 기법이 함께 사용되는 경우가 많음.

대표적으로 크루스칼 알고리즘으로 모든 간선을 정렬한 이후에 짧은 간선부터 연결하는 최소 비용 신장 트리 알고리즘이 있음.

최적의 해를 보장하지 못하는 경우 다이나믹 프로그래밍 등의 기타 알고리즘 기법을 적용해야 하기도 함.

시간복잡도

선택 정렬은 대략 N * (N+1) /2 번 가량의 연산을 수행하므로 시간 복잡도는 O(N^2)

2. 버블 정렬

개념

바로 가까이에 있는 두 숫자끼리 비교를 해서 당장 더 작은 숫자를 앞으로 보내주는 것을 반복

구현은 쉽지만 가장 비효율적인 알고리즘

시간복잡도

선택정렬과 같이 N * (N+1)/2 번 연산을 수행하므로 시간 복잡도는 O(N^2)

실제로는 매 수행마다 swap이 이루어 지기때문에 선택정렬보다도 더 느리게 된다.

3. 삽입 정렬

개념

필요할 때, 필요한 만큼만 적절한 위치에 삽입하는 정렬 방식

기본적으로 정렬이 되어있다고 가정하여 정렬함

시간복잡도

결론적으로 O(N^2) 시간복잡도를 가짐

하지만 이미 정렬된 상태에 한해서 어떤 알고리즘보다도 빠르다는 특징이 있음

4. 퀵 정렬

개념

대표적인 분할 정복 알고리즘

특정한 값을 기준으로 큰 숫자와 작은 숫자를 나누는 방식

특정 기준 값 피벗을 기준으로 그룹을 나눔

시간복잡도

평균적으로 O(N * logN)

이미 정렬이 되어 있는 경우 분할 정복의 이점을 누리지 못하기 때문에 최악의 시간 복잡도는 O(N^2)

5. 병합 정렬

개념

분할 정복 알고리즘을 이용한 일단 반으로 나누고 나중에 합쳐서 정렬하는 알고리즘

함수 안에서 배열을 선언하게 되면 매 번 배열을 선언하기 때문에 메모리 자원 낭비 차원에서 정렬에 사용되는 배열은 전역변수로 선언해야 함.

시간복잡도

최악의 상황에서도 O(N * logN)을 보장

6. 힙 정렬

개념

힙 트리 구조를 이용한 데이터 정렬 알고리즘

힙을 알려면 이진 트리를 알아야 한다.

완전 이진 트리 : 루트 노드부터 왼쪽 노드, 오른쪽 노드 순서로 채워지는 트리

힙 : 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리

최대 힙: 부모 노드가 자식 노드보다 큰 힙

힙 정렬을 수행하기 위해서는 힙 생성 알고리즘을 사용

• 힙 생성 알고리즘은 특정한 하나의 노드에 대해 수행

• 시간 복잡도 O(logN)

병합 정렬과 다르게 별도로 추가적인 배열이 필요하지 않다는 점에서 이점이 있음

시간복잡도

힙 정렬의 전체 시간 복잡도는 O(N * logN)