정렬 알고리즘 비교

출처: https://ratsgo.github.io/data%20structure&algorithm/2017/10/19/sort/

• bubble: 인접한 두개의 원소를 비교하여 자리를 교환하는 방식
  • 첫번쨰 원소부터 인접한 원소끼리 계속 자리를 교환
  • 한 단계가 끝나면 가장 큰 원소가 마지막 자리에 고정
  • 정렬이 되어있어도 모든 수를 다 확인하기 때문에 가장 비효율적인 정렬 알고리즘
• selection: 기준 위치에 맞는 원소를 선택하고 자리를 교환하는 방식
  • 원소를 돌며 가장 작은 값을 찾는다.
  • 첫번째 원소와 바꿔준다.
  • 첫번째 원소를 제외하고 원소를 돌며 가장 작은 값을 찾는다.
  • 두번째 원소와 바꿔준다. 계속 진행
  • 버블 정렬을 일부 개선함
• insertion: 정렬되어 있는 부분 집합에 정렬할 새로운 원소의 위치를 삽입하는 방식
  • 정렬된 집합 S와 정렬되지 않은 집합 U로 나눈다.
  • U에서 맨 앞의 원소를 꺼내서 S의 맨 뒤부터 비교해준다.
  • 자신 보다 작은 숫자를 만나기 전까지의 숫자와 바꿔준다.
  • 리스트가 거의 정렬된 상태라면 O(n)이라는 빠른 속도를 자랑한다.
• shell: 정렬되지 않은 배열의 경우 비효율적인 삽입정렬을 개선한 기법. 주어진 배열의 일정 간격 만큼의 요소들에 대해 삽입정렬을 반복 수행
• merge: 리스트를 분해하고 정렬하여 다시 합치는 방법 ( divide and conquer )
  • 재귀 함수를 이용하여 2개 이하로 쪼개고
  • 그 상태에서 정렬하면서 합친다.
  • 따로 메모리를 소모한다.
• heap: 힙 트리 구조를 활용하여 정렬하는 방식
  • 리스트를 완전 이진트리 구조로 만든다.
  • 최대 힙 트리를 만드는데 부모노드가 자식노드보다 큰 트리를 말한다.
  • 리스트의 첫번째와 마지막을 교환한 뒤
  • 마지막은 뺴고 위의 과정을 반복한다.
• quick: 피봇값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬
  • 왼쪽 부분집합에는 피봇값보다 작은 값들, 오른쪽 부분집합에는 피봇값보다 큰 값들
  • 부분집합의 크기가 1보다 작을 때 까지 재귀함수 반복
• counting: 입력값의 빈도를 세어 결과리스트의 인덱스로 활용하는 방식
  • 숫자 값을 인덱스로, 개수를 해당 인덱스의 값으로 한다.
  • 정렬할 숫자의 최대값(k)이 커지면 시간복잡도가 크게 증가한다.
• radix: 입력값의 자릿수(d)에 대해 각각 카운팅정렬을 적용해 카운팅정렬의 단점을 보완한 방식
• buckey: 데이터 개수만큼 버킷을 두고 데이터를 나누고 버킷별로 정렬한 후 합쳐 정렬을 완성

In-place

• 입력리스트 내부에서 정렬이 이루어지는 경우.
• 반대의 경우는 정렬 하는 중에 따로 메모리가 필요하다.
• 합병, 카운팅, 래딕스, 버킷

stable

• 값이 같은 경우 원래의 순서가 유지되는 것
• 4a,3b,5a,3a 가 있을 경우
• 정렬이 stable 할 경우 3b, 3a, 4a, 5a 처럼 3의 순서가 바뀌지 않는다.
• 반대의 경우 바뀔 수 있음

comparison

• 값을 서로 비교하는 경우
• 대부분이 비교 정렬이다.
• 카운팅, 래딕스 제외