알고리즘 - 정렬 (ing)

정렬에 대해 잘 정리된 블로그들을 보며 내가 이해하는 대로 정리하는 글. (배우면서 추가 작성 중)
정렬 알고리즘을 배우기 위해 제 게시글에 들어왔다면 원출처에 들어가서 시각적 자료들과 함께 보길 추천드립니다.
 
 
출처:

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

https://yabmoons.tistory.com/250

 

정렬별 시간복잡도

 
 

• 선택 정렬

정렬 미실행된 원소들 중 최소값을 찾아 맨 앞에서부터 채워가는 정렬
 
장점 : 구현이 쉬움, 비교횟수에 비해 교환횟수가 적어 역순정렬에 적합
단점 : 원소 추가로 인한 재정렬 시 비효율적
 
 
 

• 버블 정렬

앞에서부터 인접한 두 원소들을 비교해가며 최대값을 맨뒤로 이동시키는 정렬
 
장점 : 구현이 쉬움
단점 : 비교, 교환횟수가 많아 비효율적
 
 
 

• 삽입 정렬

(두번째 원소부터) 앞에 위치한 원소들과 비교하며 삽입해가는 정렬
 
장점 : 버블 정렬보다 비교횟수 적음, 최선의 경우 O(N)의 빠른 속도를 가짐
단점 : 최악의 경우 O(N^2)의 성능
 
 
 

• 합병 정렬

최소 비교 집합 (1, 2개 원소)이 될때까지 절반씩 분할하고 해당 원소들 정렬한 후, 인접한 집합들끼리 다시 병합해가는 정렬 (병합 시 양 집합 맨 앞에서부터 대소비교, 새로운 리스트에 정렬)
 
장점 : 안정성이 높음 (일관적인  O(nlog₂n) 복잡도)
단점 : 분할, 합병할 때마다 새로운 공간(메모리)이 필요함
 
 
 

• 퀵 정렬

 
 
 

• 힙 정렬

 
 
 

• 쉘 정렬

 
 
 

• 기수 정렬

 
 
 

• 카운팅 정렬

1 최댓값 원소+1 크기의 배열 생성 (=결과 배열) & 각 인덱스에 해당하는 원소 개수 카운팅 후 누적합 계산한 배열 생성 (=카운팅 배열)
2 (입력값 맨 뒤부터) 입력값과 일치하는 결과배열의 인덱스에 입력값 대입
3 해당 입력값과 일치하는 카운팅배열의 인덱스를 찾아 1 차감
 
장점 : 평균 O(N)의 고성능(비교계산X)
단점 : 결과배열, 카운팅배열로 인한 추가 메모리 필요, 값의 범위가 크면 비효율적일 수 있음 ex. {1,2,4,6,99999}