Selection Sort & Bubble Sort

선택정렬  Selection Sort   

 

정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 정렬되지 않은 부분의 가장 앞의 데이터와 교환해 나아가는 알고리즘이다. 

 

O(n2) 의 시간복잡도가 있다. 

 

package Sort;

public class SelectionSortTest {

	private static void selectionSort(int[] arr) {
		selectionSort(arr, 0); //시작점 
	}
	private static void selectionSort(int[] arr, int start) {
		if(start < arr.length - 1) { //시작점이 배열의 마지막보다 작은동안 재귀함수호출
			int min_index = start;  //가장 작은 인덱스를 저장할 
			for ( int i = start; i < arr.length; i++) { //시작점부터 배열의 마지막까지 돈다.
				
				if(arr[i] < arr[min_index]) min_index = i;
			}   //배열의 값이   작은배열보다 더 작으면   작은 인덱스를 업데이트한다.
			swap(arr, start, min_index);	//시작점에서 맨앞의 값과  교체
			selectionSort(arr, start + 1); //시작점에서 하나 더 가서 정렬시키기
		}
	}
	
	
	private static void swap(int[] arr, int index1, int index2) { //두개의 인덱스를 받아 스왑
		int tmp = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = tmp;
	}
	
	private static void printArray(int[] arr) {  //배열 출력 
		 for(int data : arr) {  // 향상된 for문  for(타입변수: 배열)
			 System.out.println(data + ",");
		 }
		 System.out.println();

	}
	
	public static void main(String[] args) {
		int[] arr = {3,6,1,8,2,4};  //배열선언
		printArray(arr);			//출력	
		selectionSort(arr);			//선택정렬
		printArray(arr);			//출력
	}
}

 

 

 

 

 

거품 정렬 Bubble Sort

거품정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다. 

두 인정한 원소를 교환하는 과정이 거품모양과 같다고 하여 거품정렬이라 한다. 

한번 수행할 때마다 가장 큰 값이 맨 뒤로 이동하기 때문에  요소의 개수 - 1번 반복하게 되면 모든 숫자가 정렬된다. 

 

 

O(n2) 의 시간복잡도가 있다. 

 

package Sort;

public class BubbleSortTest {

	
	private static void bubbleSort(int[] arr) {
		bubbleSort(arr, arr.length - 1);  //배열의 주소와 정렬이 안된부분에 마지막인덱스를 넘김
										  // 처음에는 정렬이 다 안된 상태이니까 -1을 준다. 
	}
	private static void bubbleSort(int[] arr, int last) {
		if(last > 0 ) {       			//마지막 인덱스가 0보다 클때가지 반복
			for(int i = 1; i<= last; i++) {
				if(arr[i-1] > arr[i]) {    //앞에 있는 것이 나보다  크다면 
					swap(arr, i -1, i);			//자리를 서로 바꾼다. 
				}
			}
			bubbleSort(arr, last -1);    //다시 호출할 때 마지막 인덱스는 빼고 정렬한다. 
		}
	}
	private static void swap(int[] arr, int source, int target) {
		int tmp = arr[source];
		arr[source] = arr[target];
		arr[target] = tmp;
	}
	
	private static void printArray(int[] arr) {
		for(int data:arr) {
			System.out.println(data + ",");
		}
		System.out.println();
		
	}	
	public static void main(String[] args) {
		int[] arr = {3,5,4,2,1};
		printArray(arr);
		bubbleSort(arr);
		printArray(arr);
		
	}
}