[알고리즘] 여러가지 정렬과 시간복잡도 (선택정렬 / 삽입정렬 / 버블정렬 / 퀵정렬 / 힙정렬 / 합병정렬)

선택정렬

• 맨 앞에서부터 차례대로 정렬하는 방법
• 주어진 리스트 중에 최소값을 찾고 그 값을 맨 앞부터 차례대로 에 위치한 값과 교체하는 방식
• 시간복잡도 : O(N^2)

선택정렬

삽입정렬

• 맨 앞에서부터 차례대로 정렬하는 방법
• 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교해서 현재 선택된 숫자의 위치를 찾아 삽입해주는 방식
• 시간복잡도 : O(N^2)

삽입정렬

버블정렬

• 첫번째 원소부터 인접한 원소끼리 비교하면서 계속 자리를 교환하면서 맨 끝부터 정렬하는 방식
• 시간복잡도 : O(N^2)

버블정렬

합병정렬

• 작은 단위로 잘게 쪼개서 작은 단위부터 정렬해서 정렬된 단위들을 계속 병합해가면서 정렬하는 방식 
• 시간복잡도 : O(NlogN)

합병정렬

퀵 정렬

• 처음 하나의 피봇(Pivot)을 정해서 이 피봇보다 작은 값은 왼쪽, 큰 값은 오른쪽에 위치시킨 뒤 왼쪽과 오른쪽은 또 다시 각각의 축으로 나누어져 축 값이 1이 될때까지 반복하면서 정렬하는 방식
• 시간복잡도 : O(N^2)

퀵 정렬

힙 정렬

• 최대 힙이나 최소 힙 트리를 구성해 정렬하는 방식
• 힙은 완전이진 트리의 형태로 리프노드를 제외한 모든 노드가 두개의 자식을 가지며, 마지막 레벨의 노드는 왼쪽부터 채워짐 
• 최대 힙은 부모가 자식보다 크고, 최소 힙은 부모가 자식보다 작은 것을 의미
• 삽입 : 항상 맨 마지막 레벨의 왼쪽에 집어넣고 부모노드와 비교하면서 자기 자리를 찾아가는 방식
• 시간복잡도 : O(NlogN)

최대 힙