[ 선택 정렬 ]
정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해가는 방식
앞에서부터 정렬됨
O(N＾2)
[ 버블 정렬 ]
이웃한 데이터를 비교하여 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방식
뒤에서부터 정렬됨
O(N＾2)
[ 삽입 정렬 ]
자신의 앞 데이터들과 비교하며 삽입을 통해 정렬하는 방식
앞에서부터 정렬됨
최악 O(N＾2)
[ 병합 정렬 ]
퀵 정렬과 같이 분할과 정복을 통해 두 개의 정렬된 배열을 합치며 더 커진 배열로 만드는 알고리즘.
좌우 두 개의 배열의 크기는 항상 동일하여 최악의 경우에도 O(NlogN)의 시간복잡도를 가진다.
두 개의 배열을 합쳐 새로운 배열을 만들기 위한 별도의 임시 기억 장치 필요.
수행 시간이 오래 걸려 주로 외부 정렬에 활용됨.
O(N*logN)
[ 퀵 정렬 ]
기준키를 기준으로 작거나 같은 값을 지닌 데이터는 기준키 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방식
평균 N*logN
최악 O(N＾2)
** 참고 사이트
https://terms.naver.com/entry.naver?docId=2270444&cid=51173&categoryId=51173
[ 힙 정렬 ]
주어진 데이터들을 이진 트리로 구성하여 정렬하는 방식.
최댓값과 최솟값을 쉽게 추출할 수 있는 완전 이진트리의 자료구조 알고리즘.
내림차순 정렬 시 최대 힙 트리 구성, 오름차순 정렬 시 최소 힙 트리 구성.
주어진 데이터를 집산의 조건을 만족하는 완전 이진 트리로 구성한 다음, 그 루트 노드를 꺼내면 그것이 데이터 중 가장 큰 값을 가지는 것이 됨.
힙 생성 O(logN)
힙 정렬 O(N)
평균 O(N log N)