Unity 내일배움캠프 TIL 1108 | 정렬 알고리즘

💡 정렬 알고리즘

🐠 정의

• 정렬 알고리즘은 데이터를 정렬하는 방법으로, 많은 양의 데이터를 효율적으로 가공하고 탐색하기 위해 사용한다.
• 대표적인 정렬 알고리즘으로는 선택 정렬, 버블 정렬, 삽입 정렬, 병합 정렬, 힙 정렬, 퀵 정렬 등이 있다.

🐬 선택 정렬

• 장점
  • 정렬을 위한 비교 횟수는 많지만 교환 횟수가 적다.
  • 교환이 많이 이루어져야 하는 상태에서 효율적으로 사용 가능하다.
  • 역순 정렬에 적합하다.
• 단점
  • 정렬을 위한 비교 횟수가 많기 때문에, 이미 정렬된 상태에서 소수의 자료가 추가되면 재정렬할 때 최악의 속도를 보인다
  • 비교 대상의 메모리 값이 정렬되어 있어도 비교 연산을 진행

🦑 버블 정렬

• 장점
  • 구현이 쉬우며 코드가 직관적이다.
  • 데이터를 하나씩 정밀 비교 가능하다.
• 단점
  • n개의 원소에 대해 n개의 메모리를 사용하므로, 원소의 개수가 많아지면 비교 횟수가 증가하여 성능이 저하된다.

🦀 삽입 정렬

• 장점
  • 버블 정렬의 비교 횟수를 줄이기 위해 고안된 정렬이다.
  • 크기가 적은 데이터 집합을 정렬할 때 효율이 좋다.
• 단점
  • 데이터 상태와 크기에 따라 성능의 편차가 크다.

🦈 병합 정렬

• 장점
  • 퀵 정렬과 다르게 기준 값에 따라 성능이 달라지는 경우가 없다.
• 단점
  • 임시 배열에 원본 값을 계속 옮겨주며 정렬하는 방식이므로 추가적인 메모리가 필요하다.
  • 추가적인 메모리를 사용할 수 없다면 병합 정렬이 아닌 퀵 정렬을 사용한다.

🐳 힙 정렬

• 장점
  • 추가적인 메모리가 필요 없다.
  • $O(n*logn)$의 시간 복잡도를 가지는 정렬 중 가장 효율적이다.
  • 항상 $O(n*logn)$의 시간 복잡도가 보장된다.
• 단점
  • 이상적인 경우 $O(n*logn)$의 시간 복잡도를 가지지만 실제로는 퀵 정렬이 더 빠르다.
  • 데이터 상태에 따라 다른 정렬들에 비해 느릴 수 있다.
  • 안정성을 보장 받지 못한다.

🐙 퀵 정렬

• 장점
  • 기준 값에 의해 분할 과정에서 $logN$이라는 시간이 소요되며, 시간 복잡도는 전체적으로 $O(n*logn)$으로 준수한 편이다.
• 단점
  • 기준 값에 따라 시간 복잡도가 크게 달라진다.
  • 안정성이 없다.

🌊 시간 복잡도 비교

알고리즘	최선	평균	최악
선택 정렬	$O(n^2)$	$O(n^2)$	$O(n^2)$
삽입 정렬	$O(n)$	$O(n^2)$	$O(n^2)$
버블 정렬	$O(n^2)$	$O(n^2)$	$O(n^2)$
병합 정렬	$O(n*logn)$	$O(n*logn)$	$O(n*logn)$
힙 정렬	$O(n*logn)$	$O(n*logn)$	$O(n*logn)$
퀵 정렬	$O(n*logn)$	$O(n*logn)$	$O(n^2)$

다음엔 정렬 알고리즘을 직접 구현해보면서 공부해봐야겠따 ..
끗~~~