정렬이란?
정렬은 특정 값을 기준으로 배열을 그 특정값의 증가나 감소하는 형태로 배열의 순서를 결정하는 알고리즘이다. 정렬 알고리즘에는 여러가지 종류가 존재한다. 이번 글에서는 어떤 종류의 알고리즘이 존재하고 여러가지 종류의 알고리즘의 장점과 단점에 대해서 설명해 보고자 한다.
버블 정렬
버블 정렬은 단순 교환 정렬이라고도 한다. 버블 정렬의 원리는 매우 매우 단순하다. 바로 옆의 숫자와 비교를 반복하는 방식이다. 배열의 가장 끝에서 부터 바로 앞 인덱스에 속한 숫자를 반복적으로 비교해 그 크기가 작으면 앞쪽으로, 크기가 크면 뒤쪽으로 보내는 알고리즘이다.
장점
구현하기 쉽다
단점
시간복잡도가 O(n^2)으로 굉장히 오래걸리는 알고리즘이고 이것은 후술하겠지만 삽입정렬과 달리 최선의 경우에도 동일하게 O(n^2)의 시간 복잡도를 가진다는 단점이 있다.
삽입 정렬
삽입 정렬은 배열의 가장 앞에서 부터 하나씩 골라 그 앞의 배열의 값을 확인하고 그 값보다 작으면 그 값과 자리를 바꾸는 것을 한다. 이것을 배열의 처음 부터 끝까지 반복하면 정렬이 완료가 된다.
장점
최선의 경우 시간 복잡도가 O(N)으로 굉장히 효율적이고 참조 지역성이 높아 안정적이다.
참조 지역성
참조 지역성이란 컴퓨터가 최근의 접근한 데이터나 그에 인접한 데이터에 접근할 가능성이 높은 데이터를 캐시 메모리에 저장하여 미리 다음 데이터에 대한 예측을 해놓는 것이다. 참조지역성이 높다는 뜻은 인접한 데이터에 반복적으로 접근하는 형태의 알고리즘이라는 뜻이다.
단점
최악의 경우 시간 복잡도가 O(N^2)으로 버블정렬과 동일한 시간복잡도를 갖는다.
합병 정렬
합병 정렬은 분할 정복의 원리를 이용하여 비교를 진행할 배열을 분할하여 쉽게 비교할 수 있는 배열의 길이가 2나 1인 배열로 만들어 개별적으로 정렬은 한 뒤 정렬이 완료된 배열을 합쳐 결과적으로는 완전히 정렬된 배열을 만들어내는 정렬방식이다.
장점
최악의 경우에도 O(NlogN)의 값의 시간복잡도를 가지고 참조지역성이 높은 알고리즘이기 때문에 알고리즘이 안정적이다
단점
배열의 크기만큼 추가적으로 메모리를 차지한다.
힙 정렬
힙 정렬은 힙 트리를 이용한 정렬 알고리즘으로 힙 트리의 특성인 가장 큰 값이 root노드로 들어간다는 특성을 이용하여 정렬을 하는 것이다. root노드의 값을 빼서 배열의 끝에 저장한 후 트리의 가장 잎사귀쪽에 있는 값을 root노드로 만들고 힙 트리를 정렬 하여 다시 root노드를 빼는 것을 반복하는 알고리즘이다.
장점
합병 정렬과 동일하게 최악의 경우에도 O(NlogN)의 값의 시간복잡도를 가지고 있지만 메모리를 추가적으로 소모하지도 않는다.
단점
트리를 만들 때 기본적으로 가장 하위노드를 root노드로 바꾸는 과정이 반복적으로 포함되기 때문에 참조지역성이 낮은 알고라즘이라 알고리즘이 불안정하다.
퀵 정렬
퀵 정렬은 피봇을 이용하여 정렬하는 알고리즘이다. 피봇을 하나 선택하여 피봇보다 크면 오른쪽, 작으면 왼쪽으로 정렬한다. 그 다음 오른쪽 배열과 왼쪽 배열에서 피봇을 하나 선택하여 이것을 반복한다.
장점
다른 모든 알고리즘에 비하여 평균적인 시간복잡도가 가장 좋고 메모리도 추가적으로 소모하지 않는다.
단점
평균적인 시간복잡도는 작지만 최악의 경우 O(N^2)의 시간 복잡도를 가져 비효율적일 수 있다.
여기까지 대표적인 정렬 알고리즘을 정리하였다. 이외에도 RB트리나 timsort와 같이 효율적인 알고리즘들이 존재하니 더 찾아보면 좋을 것같다.
