728x90
반응형
<목차>
1.정렬이란?
2. selection sort(선택정렬)
3. insertion sort(삽입정렬)
4. shell sort(셸정렬)
정렬이란?
자료를 일정한 기준에 따라 나열하는 것
큰 순서대로 정렬을 하는 오름차순과 작은 순서대로 정렬하는 내림차순이 존재
이와 관련된 여러 정렬 알고리즘이 존재
selection sort(선택정렬)
선택정렬이란 가장 작은(큰) 데이터를 찾아 가장 앞에 있는 데이터와 교환화는 방식
※데이터가 정렬이 되어 있든 없든 상관없이 일정한 시간을 가진다.
<코드>
public class selection_sort {
public static void main(String args[]) {
int[] arr = {1,5,4,2,7};
int min;
int i,j;
for(i=0; i<arr.length-1; i++) {
min = i;
for(j=i+1; j<arr.length; j++) {
if(arr[j]<arr[min])
min=j;
}
swap(arr,i,min);
}
for(i=0; i<arr.length; i++)
System.out.print(arr[i]);
}
static void swap(int[] arr, int a,int b) {
int temp;
temp =arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
}
insertion sort(삽입정렬)
삽입 정렬이란 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식
※ 데이터가 이미 정렬되어 있을 경우 시간이 빠르고 정 반대의 경우 느리다.
public class insertion_sort {
public static void main(String args[]) {
int[] arr = {1,5,4,2,7};
int i,j;
for(i=1; i<arr.length; i++)
for(j=i; arr[j]<arr[j-1]&&j>0; j--)
swap(arr,j,j-1);
for(i=0; i<arr.length; i++)
System.out.print(arr[i]);
}
static void swap(int[] arr,int i,int j) {
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
shell sort(셸정렬)
셸 정렬이란 주어진 데이터를 특정 매개변수 값의 길이를 갖는 부파일(subfile)로 쪼개서, 각 부파일에서 정렬을 수행한다. 부파일의 길이가 1이될 때까지 이 과정을 반복한다.
사용하는 이유는 삽입정렬에서 내림차순으로 정릴할 때 가장 작은 데이터가 끝에 있을 경우 많은 시간이 걸리는 것을 방지하기 위함이다.
※ 부파일로 이미 나눴기 때문에 최종적으로 부파일이 1이 되었을 때 대부분 정렬이 되어있다.
보통 부파일(h)의 길이는 h(1)=1 , h(i) = h(i-1)*3+1의 수열을 이용한다.
e.g. h1=1 h2 = 4 h3 = 13 ...
public class shell_sort {
public static void main(String[] args) {
int[] arr = {1,5,4,2,7,3,16,9};
int i,j;
int h=1;
while(true) {
if(arr.length>h*3+1)
h = h*3+1;
else
break;
}
while(h!=0) {
for(i=h; i<arr.length; i++) {
for(j=i; j-h>0&&arr[j]<arr[j-h]; j-=h)
swap(arr,j,j-h);
}
h = h/3;
}
for(i=0; i<arr.length; i++)
System.out.print(arr[i]);
}
static void swap(int []arr,int a,int b) {
int temp;
temp = arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
}
#자바 #정렬알고리즘 #선택정렬 #삽입정렬 #셸정렬
반응형
'자바' 카테고리의 다른 글
| [JAVA] 백준 2178 - 여행 가자 풀이 (0) | 2022.09.08 |
|---|---|
| [자료구조] 자바 - 큐(Queue)이란? (0) | 2021.02.02 |
| [자료구조] 자바 - 스택(Stack)이란? (0) | 2021.01.26 |
| (java)자바 너비우선탐색(BFS) (0) | 2021.01.15 |
| (java)자바 깊이우선탐색(DFS) (0) | 2021.01.14 |
