알고리즘 스터디

1. 정렬 알고리즘

1. 교환

1) 선택 정렬 알고리즘

선택정렬 알고리즘의 예제

org.reve.algorithm.sort.exchange.SelectionSortTest

정렬 준비----------
[55, 153, 4, 63, 75, 23, 53, 66, 22, 10]
정렬 시작----------
[55, 153, 4, 63, 75, 23, 53, 66, 22, 10]
[4, 153, 55, 63, 75, 23, 53, 66, 22, 10]
[4, 10, 55, 63, 75, 23, 53, 66, 22, 153]
[4, 10, 22, 63, 75, 23, 53, 66, 55, 153]
[4, 10, 22, 23, 75, 63, 53, 66, 55, 153]
[4, 10, 22, 23, 53, 63, 75, 66, 55, 153]
[4, 10, 22, 23, 53, 55, 75, 66, 63, 153]
[4, 10, 22, 23, 53, 55, 63, 66, 75, 153]
[4, 10, 22, 23, 53, 55, 63, 66, 75, 153]
정렬 완료----------
[4, 10, 22, 23, 53, 55, 63, 66, 75, 153]

선택정렬 알고리즘의 특징

비교연산 : O((n-1) + (n-2) + ... + 2 + 1) = O(n^2)
이동연산 : O(3(n-1)) = O(n)
성능 : O(n^2)
상대적으로 느린 알고리즘에 속함
자료의 연산 이동횟수가 O(n)이므로 자료의 크기가 큰 정렬에 유리
최악의 경우나 평균이나 효율성은 항상 O(n^2)
자료의 교환이 계속되므로 안정성이 없음

** 안정성(stability) : 동일한 데이터에 대해 입력한 순서대로 정렬되면 안정성이 있다고 한다.

2) 퀵 정렬 알고리즘

퀵 정렬 알고리즘의 예제

org.reve.algorithm.sort.exchange.QuickSortTest

정렬 준비----------
[55, 153, 4, 63, 75, 23, 53, 66, 22, 10]
정렬 시작----------
[4, 153, 55, 63, 75, 23, 53, 66, 22, 10]
[4, 10, 55, 63, 75, 23, 53, 66, 22, 153]
[4, 10, 55, 63, 75, 23, 53, 66, 22, 153]
[4, 10, 22, 63, 75, 23, 53, 66, 55, 153]
[4, 10, 22, 53, 75, 23, 63, 66, 55, 153]
[4, 10, 22, 53, 23, 75, 63, 66, 55, 153]
[4, 10, 22, 53, 23, 55, 63, 66, 75, 153]
[4, 10, 22, 23, 53, 55, 63, 66, 75, 153]
[4, 10, 22, 23, 53, 55, 63, 66, 75, 153]
[4, 10, 22, 23, 53, 55, 63, 66, 75, 153]
정렬 완료----------
[4, 10, 22, 23, 53, 55, 63, 66, 75, 153]

퀵 정렬 알고리즘의 특징

평균 : O(nlogn) - 피벗값이 지속적으로 자료의 중앙값이 될 때
최악 : O(n^2) - 이미 정렬된 자료에서 피벗값이 계속 끝 값이 될 때
정렬 전 자료의 상태에 따라 효율성의 차이가 큼
전체 효율성을 볼 때 상당히 우수한 성능
자료의 교환이 계속되므로 안정성이 없음
자료의 중간값을 피벗으로 사용하면 효율이 큼(중간값을 알 수 있다면)

퀵 정렬 최적화를 위한 최초의 피벗값 찾기

[1] Random - org.reve.algorithm.sort.exchange.QuickRecursiveRandomPivotSort

렌덤하게 피벗을 뽑는다.

피벗을 기준으로 피벗보다 작은값은 왼쪽으로 피벗보다 큰 값은 오른쪽으로 보낸다.

랜덤값에 따라서 O(n) ~ O(n^2) 사이의 성능을 갖는다.

[2] Median - org.reve.algorithm.sort.exchange.QuickRecursiveMedianPivotSort

왼쪽, 오른쪽, 중간에 위치한 값들 중 중간값을 피벗으로 한다

피벗을 기준으로 피벗보다 작은값은 왼쪽으로 피벗보다 큰 값은 오른쪽으로 보낸다.

3) 버블 정렬 알고리즘

버블 정렬 알고리즘의 예제

버블 정렬 알고리즘의 특징

2. 병합

1) 병합 정렬 알고리즘

병합 정렬 알고리즘의 예제

org.reve.algorithm.sort.exchange.MergeSortTest

정렬 준비----------
[80, 75, 10, 60, 15, 49, 12, 25]
정렬 시작----------
정렬범위 : 0 ~ 1 , 중간위치 : 0
[75, 80, 10, 60, 15, 49, 12, 25]
정렬범위 : 2 ~ 3 , 중간위치 : 2
[75, 80, 10, 60, 15, 49, 12, 25]
정렬범위 : 0 ~ 3 , 중간위치 : 1
[10, 60, 75, 80, 15, 49, 12, 25]
정렬범위 : 4 ~ 5 , 중간위치 : 4
[10, 60, 75, 80, 15, 49, 12, 25]
정렬범위 : 6 ~ 7 , 중간위치 : 6
[10, 60, 75, 80, 15, 49, 12, 25]
정렬범위 : 4 ~ 7 , 중간위치 : 5
[10, 60, 75, 80, 12, 15, 25, 49]
정렬범위 : 0 ~ 7 , 중간위치 : 3
[10, 12, 15, 25, 49, 60, 75, 80]
정렬 완료---------- 2ms
[10, 12, 15, 25, 49, 60, 75, 80]

병합 정렬 알고리즘의 특징

이동 및 비교 연산 횟수 : O(nlogn)
비교적 우수한 효율성을 갖는다.
정렬 전 자료의 정렬 상태에 영향을 받지 않는다.
추가 메모리 공간이 필요하다.
교환 기반 알고리즘이 아니라 안정성이 유지된다.

Reve1988/algorithm