2021년 09월 13일 TIL

정렬

https://coding-factory.tistory.com/615

선택정렬(Selection Sort)

• 앞에서부터 차례대로 정렬하는 방법
• 먼저 리스트 중 최소값을 찾고, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 진행

가장 적합한 자료형 : 역순 정렬 ( 내림 차순인 자료를 오름차순으로 정렬할때 최적 )

최악 : 이미 정렬된 상태에서 소수의 자료가 추가되는 경우 최악의 처리 속도

시간복잡도 : O(N^2)

버블정렬(Bubble Sort)

첫번쨰 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 끝부터 정렬하는 방식

N개의 원소에 대해 N개의 메모리를 사용

비교 횟수가 많으므로 비효율적

시간 복잡도 : O(N^2)

삽입 정렬(Insertion Sort)

버블정렬의 비효율성을 해결하기 위한 정렬 방식

앞에서부터 차례대로 이미 정렬된 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬 방법

버블 정렬보다 효율적, 정렬된 값은 한번도 교환이 일어나지 않고 N-1의 비교만 일어납니다.

시간 복잡도 : O(N^2)

합병 정렬(Merge Sort)

작은 단위로 잘게 쪼개어 작은 단위부터 정렬해서 정렬된 단위들을 계속 병합하며 정렬하는 방식

단점 : 데이터 전체 크기 *2 만큼의 메모리 필요

시간 복잡도 : O(nlogn)

퀵 정렬

연속적인 분할에 의한 정렬방식. 처음 하나의 축을 먼저 정하여 이 축의 값보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 위치시킨 뒤 왼쪽과 오른쪽의 수들은 다시 각각의 축으로 나누어져 축값이 1이 될 때까지 정렬합니다.

시간 복잡도 : 최선 : O(nlogn) / 최악 : O(N^2)

힙 정렬

힙 정렬은 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법입니다. 이진 완전 나무를 배열에다 접목시킨 절묘한 알고리즘입니다. 처음에는 나무 아래에서 위로 각 원소들을 최대값 힙 조건에 맞게 정리한 뒤, 나무 뿌리에 있는 자료를 차례차례 나무 뒤로 옮기면서 힙을 정렬된 배열로 바꿉니다. 뿌리에는 힙 나무 맨 뒤에 있던 원소가 왔다가, 다시 힙 조건에 맞는 위치로 내려갑니다. 시간복잡도가 O(nlogn)인 정렬 알고리즘 중에서는 부가적인 메모리가 전혀 필요없다는 게 큰 장점인 정렬 방식입니다.

쉘 정렬

삽입정렬의 개념을 확대하여 일반화한 정렬방법. 멀리 있는 레코드들끼리 비교 및 교환될 수 있으므로, 어떤 데이터가 제 위치에서 멀리 떨어져 있다면 여러 번의 교환이 발생하는 버블정렬 방식의 단점을 해결

기수 정렬

데이터의 비교를 정렬이 아닌 분산 정렬을 이용한 정렬 방법. 자릿수가 있는 데이터에만 사용 가능하다.