[알고리즘] 정렬 (bubble, straight selection, straight insertion, shell) sort...

버블 정렬

- 이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 반복하는 알고리즘

 

장점

- 구현이 간단하다

단점

- 비교 작업이 많아 연산 시간이 오래 걸림

package bublleSort;
public class bubleSort {
	static int cnt=0;
	static int[] a=new int[] {1,3,9,4,7,8,6};	
	public static void main(String[] args) {
		
		bubbleSort();
		for(int i=0;i<a.length;i++) {
			System.out.print(a[i]);
		}
		System.out.println();
		System.out.println(cnt);
	}
	static public void swap(int[] a,int i,int j){
		int temp=a[i];
		a[i]=a[j];
		a[j]=temp;
	}
	static public void bubbleSort() {
		for(int i=0;i<a.length;i++) {
			for(int j=i+1;j<a.length;j++) {
				cnt++;
				if(a[i]>a[j]) {
					swap(a,i,j);	
				}
			}
		}
	}
}

위처럼 하면 정렬이 완료되어있어도 정렬이 중간에 중단하지 못하고 끝까지 작업을 계속 진행하기 때문에 비교 작업을 계속하게 됩니다.

그래서 최적화하려면 조건을 걸어 break를 시키는 것도 방법 중 하나입니다.

static public void bubbleSort() {
		for(int i=0;i<a.length-1;i++) {
			int flag=0;
			for(int j=a.length-1;j>i;j--) {
				cnt++;
				if(a[j-1]>a[j]) {
					swap(a,j-1,j);
					flag++;//값이 변경되면 flag++				
				}	
			}		
			if(flag ==0) {//교환이 없었다는 뜻 = 정렬이 완료 되었다라는 뜻
				break;
			}
		}
	}

위 정렬로 하게 되면 비교 연산이 21이었던 게 비교 연산 횟수가 20번으로 줄어듭니다.

하지만 이것마저도 최선의 방법은 아닙니다. 최선의 방법은 마지막 교환한 요소의 인덱스 값을 기억하고 있는 것입니다.

	static public void bubbleSort() {
		for(int i=0;i<a.length-1;) {
			int lastIndex=a.length-1;//마지막으로 요소를 교환한 위치
			for(int j=a.length-1;j>i;j--) {
				cnt++;
				if(a[j-1]>a[j]) {
					swap(a,j-1,j);
					lastIndex=j;//교환한 마지막인덱스 값저장			
				}	
			}		
			i=lastIndex;//수행할 패스의 범위 제한
		}
	}

이 최적화 방법을 사용하게 되면 비교 연산이 12회밖에 진행되지 않는다. 버블 정렬을 사용하려면 위 방법처럼 최적화시켜서 사용하는 게 제일 좋다.

선택 정렬

선택 정렬은 가장 작은 요소를 맨 앞으로 이동하고, 두 번째 작은 요소를 맨 앞에서 두 번째로 이동하는 등의 작업을 반복하는 알고리즘

static void select() {
		for(int i=0;i<a.length-1;i++) {
			int min=i; //정렬되지않는 부분에서 제일작은 인덱스값 저장
			for(int j=i+1;j<a.length;j++) {
				if(a[min]>a[j]) {
					min=j;// 제일 요소가 작은값이 min값
				}
			}
			swap(a,i,min);//정렬 되지 않은 부분의 첫요소와 가장작은 요소를 교환			
		}
	}

 

선택정렬결과

삽입 정렬

삽입 정렬은 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘입니다.

static void insertion() {
		for(int i=1;i<a.length;i++) {
			int temp=a[i];
			int j;
			for(j=i;j>0&&a[j-1]>temp;j--) {
				a[j]=a[j-1];				
				}
			a[j]=temp;	
			}
	}

삽입 정렬 예시 영상

https://www.youtube.com/watch?v=EdIKIf9mHk0 

insert sort예시

위 3가지 단순 정렬의 시간 복잡도는 모두 O(n^2)

 

셸 정렬

shell sort은 삽입 정렬의 장점을 살리고 단점을 보완하여 좀 더 빠르게 정렬하는 알고리즘이다.

아래는 shell 정렬의 예시이다.

 

 

 

https://www.youtube.com/watch?v=CmPA7zE8mx0

 

아래는 코드로 구현한 것이다.

static void shellSort() {
		int halfSize=a.length/2; //일정한 간격으로 두요소로 묶기 위해	
		for(;halfSize>0;halfSize/=2) {//간격을 좁혀 그룹의 수를 줄이면서 정렬 반복
			for(int i=halfSize;i<a.length;i++) {
				int temp=a[i];
				int j;
				for(j=i-halfSize;j>=0;j=j-halfSize) {// 그룹끼리 비교하기 위해
						if(a[j]>temp) {
							a[j+halfSize]=a[j];
						}else {
							break;
						}					
					}				
				a[j+halfSize]=temp;				
				}
		}		
		//printSort();
	}

아래 사진은 내가 이해하려고 손 코딩으로 풀이한 것 

4- 정렬

2- 정렬

 

혼자서 알고리즘을 생각하여 정렬을 만드는 게 너무 머리가 아프고 힘든 것 같다. 이 정렬에 익숙해져서 알고리즘을 외우고 이해하는 것이 필요할 것 같다. 손으로 일일이 풀이하면서 이해하도록 해야겠다