[자료구조 알고리즘] 자료구조 효율적인 탐색을 위한 정렬알고리즘#2

[구현한 코드]

- https://github.com/imjinbro/datastructure/tree/master/src/main/java/com/jinbro/source/sorting

- 이제 배운 정렬 알고리즘으로 여러 데이터를 정렬해봐야지

[병합정렬]

1) 큰 문제를 더이상 쪼갤 수 없을 떄까지 쪼개서 해결(정렬)하면서 결합

- 결합하면서 정렬 : 1개까지 쪼개버려서 정렬하면서 붙임(완전 단순화)

- 실제로 쪼개는게 아니라 접근 제한

(1) 쪼갤 수 있을 떄까지 쪼개고

(2) 최소한의 상태로 쪼개진 2개를 가지고 정렬 - 병합

2) 성능 :  NlgN (데이터 N개 일 때 최악의 경우 얼마나!)

- 연산 : 분할(나눠) + 병합(비교 정렬 후 합치기) - 둘 중에 병합 평가만 일단

(1)병합 단계가 데이터 개수에 따라 달라짐

- 8개일 때 - 1 1 1 1 1 1 1 1 -> 2 2 2 2 -> 4 4 -> 8 (3단계)

(2)병합 각각의 단계에서 비교연산을 얼마나 하나?

- 최대 단계에 있는 개수만큼(남은 것도 추가하는 것까지)

[퀵소트]

1) 기준점(pivot)을 기준으로 왼쪽, 오른쪽 정렬함

- 큰 단위에서 작은 단위로 좁혀들어가면서 위의 과정을 반복함 : 재귀

2) 구현할 때 고려해야할 것

- 피벗선택 : 피벗에 따라 성능이... 가급적 중간값을 골라야(성능평가를 보면 압니다)

- 중복값에 대한 처리도 생각해야함 : 피벗과 같은 값일 때

- 값 탐색할 때 배열 범위를 벗어나지않도록 : 4 4 3 정렬이라고 생각하면 findHigh(왼->오 탐색)이 right에 도달 했을 때 종료되어야함을 알 수 있음

3) 피벗선택 : 지금 코드는 맨 앞에 요소를 피벗으로

- 샘플링 : 샘플 뽑아서 그 중에 중간값으로 : 뽑기 + 비교 연산을 반복도 아니고 1번씩해서 퀵소트 연산을 조금 더 효율적으로

4) 성능평가

(1) 최선 : 피벗이 중간값인 경우

- 차수(진행) : 8개 데이터 -> 4개 데이터 -> 2개 데이터 -> 1개 데이터 - 8개일 때 3차 진행

- 비교 : low와 high가 교차될 때까지 n번

- nlgn

(2) 최악 : 피벗이 순서상 양 끝값인 경우

- 하나씩 빠져나가는 형태 : n개일 때 n차

- 비교 연산 n

- n^2

[기수정렬]

- 데이터와 데이터를 비교하지않고 정렬하는 알고리즘

- 자리수에 맞는 버킷을 찾아가는 정렬 : 대소 비교가 되어버림

- 데이터 자리자리를 비교할 수 있는 동일 타입 데이터여야함 : 기수(데이터 구성하는 기본요소)

(1) 동일한 길이면 좋음!

(2) 정수라면 양의정수, 음의정수 같이 있다면 같은 부호로 만드는 가공작업을.. : 성능상에는 가공작업이 붙어서

- 방법

(1) LSD : 왼쪽값이 모두 같다는 가정하에 오른쪽 값부터 정렬

(2) MSD : 높은자리부터 정렬(보통 왼 -> 오) - 단계별로 정렬 후에 같은 버킷에 들어간 데이터끼리 정렬해야함

- 구현 : 버킷의 입구와 출구가 나뉨 + FIFO = 큐

- 성능평가

(1) 연산 : 데이터 삽입과 추출(같음)

(2) 데이터 N개, 최대 길이 M만큼 -> O(MN)

[힙정렬]

1) 힙을 이용한 정렬 후 탐색

- 우선순위에 의한 정렬

2) 성능 : 힙(완전이진트리)를 그려봅시다

- 주요연산 : 저장, 삭제 - 어느 자리에 저장할 것인가, 삭제 후 정렬을 어떻게 할 것인가

- 워스트케이스 : 트리 높이만큼 비교 연산

- 시간복잡도 : 2개 중 비교, 1회에 2개를 비교, N회 2^n개 비교

            저장 삭제 각각 N개 일 때 - Nlog2N