생각을 개발하자, 박진형

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

Data structure & Algorithm/data structure_algorithm

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

imjinbro imjinbro 2017.11.17 12:26

[구현한 코드]

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