[알고리즘/정렬] 간단한 정리_Bubble sort / Selection sort / Insertion sort / Merge sort / Heap sort / Quick sort
#TODO : Count sort / Radix sort
버블 정렬(Bubble sort) 이란?
옆에 있는 값과 비교하여 더 큰 값을 반복적으로 뒤로 보내는 정렬 알고리즘.
시간복잡도 O(N^2)
Process
- 한 칸씩 인접한 자료값을 비교하여, 큰 값이 뒤로 가도록 교환한다.
- 한번 끝까지 자료 탐색이 되면, 현재 iteration 에서 가장 큰 값이 맨뒤로 이동된다.
- 더이상 정렬할 것이 없을 때 까지 반복한다.
선택 정렬(Selection sort) 이란?
각 배열 위치에 순차적으로 어떤 원소를 넣을지 선택하여 정렬하는 알고리즘.
시간복잡도 O(N^2)
Process
- 주어진 배열 중에서 최솟값을 찾는다.
- 해당 최솟값을 맨 앞에 위치한 값과 교체한다.
- 처음 위치를 제외한 나머지 리스트 요소들을 같은 방법으로 교체한다.
- 더이상 정렬할 것이 없을 때 까지 반복한다.
삽입 정렬(Insertion sort) 이란?
각 배열 위치에 순차적으로 어떤 원소를 넣을지 선택하여 정렬하는 알고리즘.
배열이 클 경우 적합하지 않다. --> 비교적 많은 이동이 필요
시간복잡도 O(N^2)
- 자료가 정렬되어있는 경우, O(N) --> 이동 없이 1번의 비교만 이루어질 경우.
- 자료가 역순인 경우, O(N^2).
Process
- 두번째 부터 시작(key)하여, 그 앞의 자료들과 비교해 삽입할 위치를 지정한다.
- 지정된 위치에 자료를 삽입한다.
- 다음 키로 이동한 후, 이전 회전결과 요소들을 순차로 비교하며 삽입한다.
- 더이상 정렬할 것이 없을 때 까지 반복한다.
합병 정렬(Merge sort ) 이란?
대표적인 안정 정렬 --> 상용 라이브러리에서 많이 사용되어지고 있다.
분할정복 알고리즘 (분할, 정복, 조합 단계를 거쳐 문제를 해결한다.)
분할 : 문제를 동일한 유형의 여러 하위 문제로 나눈다.
정복 : 가장 작은 단위의 하위문제를 해결하여 정복한다.
조합 : 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.
최선과 최악 모두 O(nlogn)
일반 배열을 통한 구현보다, 링크드 리스트를 통한 구현이 어떠한 정렬 알고리즘보다 효과적이다.
시간복잡도 O(NlogN)
Process
- 입력 배열을 더이상 나누지 못할 때 까지 2개로 나눈다. (각 요소 크기가 1이 될 때 까지)
- 각 부분 배열들을 정렬한다.
- 정렬된 부분 배열들을 하나의 배열로 합친다.
- 모든 부분 배열들이 하나가 될때 까지 합친다.
힙 정렬(Heap sort) 이란?
최대 힙 트리나 최소 힙 트리를 사용한 정렬 알고리즘.
가장 큰 값 몇개만 필요할 때 힙정렬은 매우 효과적이다.
시간복잡도 O(NlogN)
Process
- 정렬 할 요소들로 최대 힙 or 최소힙(완전 이진 트리 형태)를 만든다.
- 만들어진 힙에서 요소를 하나씩 꺼내어 배열에 순서대로 저장한다.
퀵 정렬(Quick sort ) 이란?
합병 정렬과 같은 분할 정복 알고리즘.
하지만, 불안정 정렬이다(피벗선정 기준에 따라 속도가 달라진다).
피벗을 기준으로 왼쪽, 오른쪽 구역을 나누며 정렬한다.
먼거리의 데이터를 교환가능하고, 불필요한 데이터의 이동을 줄였기 때문에 다른 O(NlogN) 정렬 알고리즘 보다 빠르게 수행된다.
시간복잡도 평균 O(NlogN)
- 자료가 정렬되어있는 경우 & 자료가 역순인 경우, 최악 O(N^2) --> 피벗 선택 위치에 따라 해결 가능.
Process
- 정렬 요소들 중 하나를 피벗으로 정한다 (가장 첫번째 or 중간 or 가장 끝 or 랜덤 지정).
- 피벗 기준으로 리스트를 나눈다.
- 양 끝(left, right)에서 부터 순차 탐색을 진행하며 피벗을 기준으로 왼편은 피벗보다 작은값, 오른편은 피벗보다 큰값으로 left, right 요소를 교환한다.
- 탐색된 left right의 인덱스값이 서로 엇갈리게 되면 탐색을 중지.
- 중지된 위치에서 피벗을 중지된 위치로 교환한다.
- 나누어진 분할 영역에 대해 재귀적으로 반복한다.