selection sort(선택정렬),insertion sort(삽입정렬),shell sort(셸정렬)

<목차>

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;
	}
}

 

 

 

 

#자바 #정렬알고리즘 #선택정렬 #삽입정렬 #셸정렬