Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- zipkin
- Serial GC
- 생산자 소비자 패턴
- Spring Boot Actuator
- 멀티스레드
- TypeScript
- 배치
- The law of Demeter
- 체인 패턴
- spring cloud
- 사가 패턴
- 알고리즘
- 스프링 배치
- Java
- 키클락
- 타입스크립트
- thread
- Resilinece4j
- 디자인패턴
- Parallel Old GC
- java 정렬
- JPA
- Action Pattern
- Spring Cloud Netfilx Eureka
- MSA
- saga pattern
- 디자인 패턴
- Transaction Pattern
- spring batch
- 스레드
Archives
- Today
- Total
PSD( Private-Self-Development )
쉘 정렬( Shell sort ) 알고리즘 본문
쉘 정렬 알고리즘?
삽입 정렬을 보완한 알고리즘
정렬 절차
- 먼저 정렬해야 할 리스트를 일정한 기준( ex. 일정 간격 마다 자른다 )에 따라 분류
- 연속적이지 않은 여러 개의 부분 리스트를 생성
- 각 부분 리스트를 삽입 정렬을 이용하여 정렬
- 모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 반복
- 위의 과정을 부분 리스트의 개수가 1이 될 때까지 반복
특징
장점
- 삽입 정렬 보다 성능이 좋다.
- 삽입 정렬의 단점인 레코딩 이동이 많은 점을 보완
- 알고리즘이 간단하여 쉽게 구현 가능하다.
구현
public static void shellSort( int[] target ){
shellSort( target, getGap( target.length ) );
}
public static int getGap( int target ){
int nextGap = target / 2;
if( target % 2 == 0 ){
nextGap++;
}
return nextGap;
}
public static void shellSort( int[] target, int gap ){
// gap 이 1 이면 그만!
if( gap == 1 ){
return;
}
// 리스트 개수
int partNum = target.length / gap;
if( target.length % gap != 0 ){
partNum++;
}
// 리스트 별로 시작, 종료 인덱스 설정 후 삽입 정렬
for( int i = 0; i < partNum; i++ ){
int firstIndex = i*gap;
int endIndex = (i+1)*gap-1;
if( target.length < endIndex ){
endIndex = target.length-1;
}
// 삽입 정렬
shell_insertionSort( target, firstIndex, endIndex );
}
// 재귀
shellSort( target, getGap( gap ) );
}
public static void shell_insertionSort( int[] target, int firstIndex, int endIndex ) {
for( int i = firstIndex + 1; i <= endIndex; i++ ){
int pick = target[i];
int j;
for( j = i-1; j >= 0 && target[j] > pick; j-- ){
// 오른쪽이동
target[j+1] = target[j];
}
target[j+1] = pick;
}
}
시간 복잡도
최상 : n
평균 : n^1.5
최악 : n^2
참고
https://gmlwjd9405.github.io/2018/05/08/algorithm-shell-sort.html
'Backend > 알고리즘' 카테고리의 다른 글
퀵 정렬( Quick sort ) 알고리즘 (0) | 2022.12.16 |
---|---|
병합 정렬( Merge sort ) 알고리즘 (0) | 2022.12.15 |
삽입 정렬( Insertion sort ) 알고리즘 (0) | 2022.12.12 |
선택 정렬( Selection sort ) 알고리즘 (0) | 2022.12.12 |
버블 정렬( Bubble sort ) 알고리즘 (0) | 2022.12.12 |