java 기초 공부 내용 정리(컬렉션 프레임웍-정렬)

정렬 알고리즘

데이터를 순서대로 나열하기 위한 절차적인 과정

정렬알고리즘의 종류

1. 선택정렬(Selection Sort)
   최소값 혹은 최대값을 선택해서 가장 앞에다가 위치하여 선택할 위치를 이동하며 정렬하는 방법
   1) 장점: 구현이 쉽다.
   2) 단점: 다른 정렬에 비해 시간이 오래 걸린다.

정렬 알고리즘 진행 코드
	public static void main(String[] args) {
		int ar[]= {8,1,2,5,4,3,6,7};
		int min, tmp;
		
		System.out.println("--------정렬 전--------");
		for(int i=0;i<ar.length;i++) {
			System.out.print(ar[i]+ " ");
		}
		for(int i = 0;i<ar.length-1;i++) {
			min=i;
			for(int j=i+1;j<ar.length;j++) {
				if(ar[min]>ar[j]) {
					tmp=ar[min];
					ar[min]=ar[j];
					ar[j]=tmp;
					
					System.out.println();
					System.out.println("swap 후!");
					for(int k =0;k<ar.length;k++) {
						System.out.print((ar[k]+" "));
					}
					
				}
			}
		}
		System.out.println();
		System.out.println("--------정렬 후--------");
		for(int i =0;i<ar.length;i++) {
			System.out.print((ar[i]+" "));
		}
	
	}

}

## 출력값
--------정렬 전--------
8 1 2 5 4 3 6 7 
swap 후!
1 8 2 5 4 3 6 7 
swap 후!
1 2 8 5 4 3 6 7 
swap 후!
1 2 5 8 4 3 6 7 
swap 후!
1 2 4 8 5 3 6 7 
swap 후!
1 2 3 8 5 4 6 7 
swap 후!
1 2 3 5 8 4 6 7 
swap 후!
1 2 3 4 8 5 6 7 
swap 후!
1 2 3 4 5 8 6 7 
swap 후!
1 2 3 4 5 6 8 7 
swap 후!
1 2 3 4 5 6 7 8 
--------정렬 후--------
1 2 3 4 5 6 7 8 

2. 삽입정렬(Insertion Sort)
   지정한 값의 삽입할 위치를 찾아 정렬하는 방법

	public static void main(String[] args) {
		int ar[]= {8,1,2,5,4,3,6,7};
		int idx, tmp;
		System.out.println("------정렬전-------");
		for(int i=0;i<ar.length;i++) {
			System.out.print(ar[i]+" ");
		}
		System.out.println();
		for(int i=1;i<ar.length;i++) {
			idx=i;
			for(int j=i-1;j>=0;j--) {
				if(ar[j]>ar[idx]) {
					tmp=ar[j];
					ar[j]=ar[idx];
					ar[idx]=tmp;
					idx=j;
					for(int k=0;k<ar.length;k++) {
						System.out.print(ar[k]+" ");
					}
					System.out.println();
				}
				else {
					break;
				}
			}
		}
		System.out.println("------정렬 후------");
		for(int i=0;i<ar.length;i++) {
			System.out.print(ar[i]+ " ");
		}
	
	}

}


## 출력값
------정렬전-------
8 1 2 5 4 3 6 7 
1 8 2 5 4 3 6 7 
1 2 8 5 4 3 6 7 
1 2 5 8 4 3 6 7 
1 2 5 4 8 3 6 7 
1 2 4 5 8 3 6 7 
1 2 4 5 3 8 6 7 
1 2 4 3 5 8 6 7 
1 2 3 4 5 8 6 7 
1 2 3 4 5 6 8 7 
1 2 3 4 5 6 7 8 
------정렬 후------
1 2 3 4 5 6 7 8 

3. 버블정렬(Bubble Sort)
   인접한 두 수를 비교해서 큰 수를 뒤로 보내는 알고리즘
   정렬과정이 거품이 일어나는 것과 비슷하여 버블이라고 부름
   1) 장점: 구현이 쉽고 코드가 직관적이다.
   2) 단점: 시간이 오래걸리고 최선, 최악, 평균 모두 O(n^2)이라는 시간 복잡도를 가진다.

	public static void main(String[] args) {
		int ar[]= {6,4,7,9,1};
		int tmp;
		
		System.out.println("------정렬 전-------");
		for(int i=0;i<ar.length;i++) {
			System.out.print(ar[i]+" ");
		}
		System.out.println();
		for(int i=ar.length-1;i>=0;i--) {
			for(int j=0;j<i;j++) {
				if(ar[j]>ar[j+1]) {
					tmp=ar[j];
					ar[j]=ar[j+1];
					ar[j+1]=tmp;
					for(int k=0;k<ar.length;k++) {
						System.out.print(ar[k]+" ");
					}
					System.out.println();
				}
			}
		}
		
		System.out.println("-----정렬 후-----");
		for(int i=0;i<ar.length;i++) {
			System.out.print(ar[i]+" ");
		}
		System.out.println();
	
	}

}

## 출력 값
------정렬 전-------
6 4 7 9 1 
4 6 7 9 1 
4 6 7 1 9 
4 6 1 7 9 
4 1 6 7 9 
1 4 6 7 9 
-----정렬 후-----
1 4 6 7 9