선택정렬, 삽입정렬, 버블정렬 (1/21)

기본 정렬 알고리즘

1/ 선택정렬: 최솟값을 찾아 교환

private static void selection_sort(int[] a, int size) {
	for(int i=0; i<size-1; i++) {
		int min_index = i;
		
		//최솟값을 갖고있는 인덱스 찾기
		for(int j = i+1; j<size; j++) {
			if(a[j] < a[min_index]) {
				min_index = j;
			}
		}
		// i번째 값과 최솟값을 서로 교환
		int tmp = a[i];
		a[i] = a[min_index];
		a[min_index] = tmp;
	}
}

 

2/ 버블정렬:

바로 옆의 element와 비교해서 정렬.

public void bubbleSort(int[] numbers) {
		
	//자기 옆의 원소와 비교하는 코드 작성
	for(int k=0;k<numbers.length;k++) {
		boolean flag = false; //비교문 안에 들어갔니? 정렬이 다 끝났으면 종료
		for(int i=0;i<numbers.length-1;i++) {
			if(numbers[i]>numbers[i+1]) {
				int temp = numbers[i];
				numbers[i] = numbers[i+1];
				numbers[i+1] = temp;
				flag = true;
			}	
		}
		if(!flag) {
			break;
		}
		System.out.println(Arrays.toString(numbers));
	}
}

 

3/ 삽입정렬:

최솟값을 찾은 다음, 최솟값이 있던 자리에 그 앞의 값을 그 자리에 넣고, 한 칸씩 밀려서 넣은 다음, 기준 값 자리에 최솟값을 넣음.

public void insertSort(int[] numbers) {
	for(int i=0;i<numbers.length-1;i++) {		//처음 숫자부터 시작. 마지막에서 그 전 숫자까지 비교
		for(int j=i+1;j<numbers.length;j++){	//비교 숫자 결정. 두 번째 숫자부터 마지막 숫자까지
			if(numbers[i]>numbers[j]) {			//두 개 숫자 비교. 앞의 숫자가 더 크면 바꿀 준비
				int temp = numbers[j];			//작은 숫자를 temp에 저장
				for(int k=j;k>i;k--) {			//큰 숫자 바로 뒤까지 숫자 밀도록
					numbers[k] = numbers[k-1];	//작은 숫자의 자리에 그 앞에 있는 숫자를 넣음. 그래서 한 칸씩 밀리게.
				}
				numbers[i] = temp;				//작은 숫자를 i 자리에 삽입
				System.out.println(Arrays.toString(numbers));	//새로운 배열 출력
			}
		}
	}
}