[bubble sort]
인접 값끼리 비교하며 정렬. i를 length-i-1까지 올리는 정렬
장점 : 구현이 간단하다. 코드가 직관적이다.
단점 : 정렬 시간이 오래 걸린다. 최악최선 모두 O(N^2)의 시간복잡도를 갖긱에 효율적인 정렬 방법은 아니다.
어떤 상황에 쓸까?
이미 정렬된 데이터를 정렬 시에 가장 빠르다.(반대로 역순 배열은 가장 느리다.)
[insert sort]
standard에 i번째 값을 넣어두고 standard보다 비교하여 크다면 작은 것이 나올 때까지 미루고 그자리에 넣는다.
장점 : 최선의 경우 O(n)으로 정렬이 가능하다.
단점 : 최악의 경우 O(n^2)이 걸린다. 데이터의 상태, 크기에 따라 성능의 편차가 심하다.
어떤 상황에 쓸까?
이미 정렬된 경우, 최고의 정렬 알고리즘. 탐색을 제외한 오버헤드가 매우 적다.
[merge sort]
분할 분할 분할 정복 정복 정복(퀵 정렬과 비슷하게 원본 배열을 분할하면서 정렬하는 정렬법)
장점 : 항상 O(nlogn)으로 일정한 속도로 정렬된다. 퀵 정렬과 다르게 피벗을 설정하는 과정이 없이 무조건 절반으로 분할하기에 피벗에 따라 성능이 안 좋을 일은 없다.
단점 : 추가적인 메모리 공간이 필요하다. 임시 배열에 원본 맵을 계속해서 옮겨주면석 정렬하는 방법이기 때문에 정렬이 완료되면 원래 맵으로 결과를 복사해야 하므로 시간 복잡도가 더 높아질수 있다.
어떤 상황에서 쓸 까?
작은 데이터 세트에서만 효과적이다. 만약 대규모 데이터 세트를 처리해야 할 때는 다른 알고리즘을 고려해야 한다.
[quick sort()]
피벗을 정하고 피벗 보다 작으면 왼쪽, 크다면 오른 쪽. 계속 비교하면서 교환
장점 : 평균 실행시간 O(nlogn)으로 빠른 편이다.(분할 과정에서 logn이라는 시간이 걸린다.)
단점 : Pivot에 따라서 성능의 차이가 심하다. 최악의 경우 O(n^2)가 걸린다.
(in-place)불안정 정렬이다.
어떤 상황에서 쓸 까?
순차 접근이 아닌 임의 접근이기때문에 linkedlist를 퀵 정렬에 사용하면 성능이 좋지 않다.
cf)linked list는 요소가 가리키는 포인터를 가지고 있다. 따라서 일반적인 배열과 달리 linked list를 사용하게 된다면 인덱스를 통해서 바로 접근할 수 없기 때문에 특정 위치에 존재하는 피벗을 바로 찾을 수 없고 처음 부터 순회해서 찾아야 하는 문제점이 발생하게 된다.
[heap sort]
이진트리를 기반으로 하는 자료구조
heapsort는 주어진 배열을 Max Heap으로 변환한 다음, 최대값을 뽑아내서 배열의 끝으로 이동시키고, 다시 Max heap을 만들어 반복적으로 최대값을 뽑아내면서 정렬하는 과정을 반복한다.
First step. Max Heap으로 변환한다
ex)루트 노드와 자식 노드를 비교하여, 자식 노드의 값이 더 크면 루트 노드와 자식 노드를 교환한다.
다시 루트 노드와 자식 노드를 비교하여, 자식 노드의 값이 더 크면 루트 노드와 자식 노드를 교환한다.
마지막으로 루트 노드와 자식 노드를 비교하면서, 자식 노드의 값이 더 큰경우 교환한지 않는다.
Second step. 최대값 뽑아내기
ex)Max heap에서 최대값을 뽑아내서 배열의 마지막 요소와 교환한다.
Third step. Max heap 만들기
ex)배열의 처음부터 끝에서 두 번째 요소까지를 Max heap으로 변환하고 이진트리 형태로 배열한다. 루트노드와 자식노드를 비교하여, 자식노드의 값이 더 크면 루트노드와 자식노드를 교환한다.다시 루트노드와 자식노드를 비교하여...이러한 과정을 반복한다.
장점 : 항상 O(nlogn)으로 빠른 편이다.
단점 : 다른 O(nlogn)의 정렬법보다 오래걸린다. 이상적으로는 퀵 정렬과 똑같이 나오지만 실제로는 퀵정렬보다 느리다. 데이터 상태에 따라 다른 정렬법에 비해 느린편이다.
(in-place)불안정 정렬이다.
어떤 상황에서 쓸까?
가장 크거나 가장 작은 값을 구할 때
최대 K만큼 떨어진 요소들을 구할 때
[selection sort]
standard로 값을 i로 저장하고 i보다 작으면 standard를 바꾸면서 바꾸면서 반복. 이 후 교환
장점 : 구현이 간단하다. 비교하는 횟수에 비해 교환이 적게 일어난다.
단점 : 정렬 시간이 오래 걸린다. 항상 O(n^2)의 시간 복잡도를 갖지만 실제로는 버블 정렬 보단 빠르다.
어떤 상황에 쓸까?
비교 횟수에 비해 적은 교환 횟수를 갖기에 많은 교환이 일어나야 하는 자료 상태에서 비교적 효율적
[shell sort]
insert sort의 성능을 향상시키기 위해 개발된 정렬 알고리즘이다. 배열을 일정한 간격으로 분할하여 각 구간을 삽입정열하고, 이후 간격을 점점 줄여가며 구간을 다시 삽입 정렬하는 것이다. 간격은 보통 배열 길이의 반으로 시작하여 점점 줄여나간다.
1.초기 간격 설정
ex)배열의 길이가 6이라면 초기 간격을 3으로 설정한다.
각 배열을 3개씩 묶어 각각 삽입 정렬한다.
2.간격을 줄인다.
ex)간격을 3에서 1로 줄인다.
배열을 1개씩 묶어 각각 삽입정렬을 한다.
간격을 3에서 1로 줄인다.
장점 : O(nlogn)의 정렬법보다 빠르다.
단점 : 설정 간격에 따라 성능의 차이가 심하다.(간격을 수학적으로 산출해야 한다.)
어떤 상황에서 쓸까?
대부분의 데이터가 이미 정렬되어 있는 경우, 데이터가 무작위로 분포되어 있는 경우, 데이터의 양이 적은 경우, 안정성이 필요한 겨우
[radix sort()]
정렬할 데이터를 자릿수 별로 비교하여 정렬하는 알고리즘이다.
Ex) 3자리 수를 기준으로 정렬한다고 가정한다면 1의 자리수를 비교하여 정렬하고 다음에는 10의 자리 수를 비교하여 다시 정렬한다. 마지막으로 100의 자리 수를 비교하여 정렬한다 이렇게 하면 3자리 수를 기준으로 정렬할 수 있다.
cf)작은 자릿수부터 비교하여 정렬하는 LSD방식과 큰 자릿수부터 비교하여 정렬하는 MSD방식으로 구분된다.
장점 : O(N) 속도로 굉장히 빨리 정렬할 수 있다. 안정적인 알고리즘이다.
단점 : 정렬하려는 데이터의 특성에 대한 추가 정보가 필요하다.(예를 들어 정렬하려는 데이터가 숫자인 경우 자릿수에 대한 정보가 필요하고 이 정보를 바탕으로 자릿수 별로 정렬을 수행한다.), 메모리 사용량이 크다.
어떤 상황에서 쓸까?
정렬하려는 데이터의 범위가 제한적이라면 성능적으로 우수한 알고리즘이다.
유의해야 할 점은 데이터의 범위가 매우 크거나 데이터가 문자열일 경우에는 성능이 저하될 수 있다.
