[Algorithm] 정렬 Sort - Selection sort , Bubble sort , Insertion sort

Selection Sort (선택 정렬)

• 최대 원소를 찾아 맨 오른쪽 원소와 자리를 바꿈 
• 맨 오른쪽으로 이동한 원소를 무시한채로 위의 루프 실행을 반복

구현

• 크기가 큰 원소를 오른쪽부터 정렬
• 크기가 작은 원소를 왼쪽부터 정렬
• 위의 두가지 방식으로 구현 가능 

public class Sort_selectionSort {
	private static int data[] = {7, 1, 3, 5, 9, 2};
	
	//최대 원소를 맨 오른쪽으로 이동시키며 정렬
	public static void selectionSortMax(int[] data, int length) {
		int max; //값이 최대인 원소
		int temp;
		for(int i=data.length-1; i>0; i--) { //맨 오른쪽 원소부터 왼쪽에서 두번째 원소까지 탐색
			max = i; //정렬이 완료된 부분을 제외한 맨 오른쪽 원소를 max라고 가정
			for(int j=i-1; j>=0; j--) { //값이 최대인 원소를 찾기 위한 루프
				if(data[max] < data[j])
					max = j;
			}
			temp = data[i];
			data[i]= data[max];
			data[max] = temp;
		}
	}
	
	//최소 원소를 맨 왼쪽으로 이동시키며 정렬
	public static void selectionSortMin(int[] data, int length) {
		int min; //값이 최소인 원소
		int temp;
		for (int i=0; i<length-1; i++) { //맨 왼쪽 원소부터 오른쪽에서 두번째 원소까지 탐색
			min = i;
			for(int j=i+1; j<=length-1; j++) { //정렬이 완료된 부분을 제외하고 맨 오른쪽 원소까지 탐색
				if(data[j] < data[min])
					min=j;
			}
			temp = data[i];
			data[i] = data[min];
			data[min] = temp;
		}
	}
	
	public static void main(String[] args) {
		 selectionSortMin(data, data.length);
		 for(int a : data) {
			 System.out.print(a + " ");
		 }
	}

}

 

---

Bubble Sort (버블 정렬)

• 가장 왼쪽 원소부터 바로 오른쪽의 원소와 크기를 비교하여 크기가 더 큰 원소를 오른쪽으로 이동
• 위의 단계를 한 루프 실행 시 결과적으로 값이 최대인 원소가 맨 오른쪽으로 이동
• 정렬이 완료될 때까지 루프 반복 실행

구현

• 정렬이 완료된 부분은 제외하고 남은 원소들 중 연속 두개의 원소를 비교해가며 정렬

public class Sort_bubbleSort {
	private static int data[] = {7, 1, 10, 3, 5, 9, 2};
	
	private static void bubble(int[] data, int length) {
		for(int i=length-1; i>0; i--) { //정렬이 완료된 부분은 제외
			for(int j=0; j<i; j++) { //정렬이 완료되지 않은 부분 중 맨 왼쪽부터 비교
				if(data[j] > data[j+1]) { //연속 두개의 원소를 비교
					int temp = data[j];
					data[j] = data[j+1];
					data[j+1] = temp;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		bubble(data, data.length);
		for(int a : data) {
			System.out.print(a + " ");
		}
	}
}

 

---

Insertion sort (삽입 정렬)

• 처음 key 값은 두번째 자료에서 시작 (원소가 하나일 때는 정렬되어 있다고 봄)
• 새로운 원소를 정렬된 배열에 삽입해가며 정렬시키는 방법

• 삽입할 데이터를 임시변수에 저장
• 이미 정렬된 데이터들의 젤 오른쪽 값부터 삽입할 데이터와 비교하여 정렬 진행
• 오른쪽 데이터부터 비교할 경우 데이터 비교와 이동을 한번에 할 수 있기 때문에 효율성이 좋음

구현

• 두번째 원소를 key로 시작하여 key 원소 기준 왼쪽의 값들과 크기를 비교하여 정렬

public class Sort_insertionSort {
	private static int data[] = {7, 1, 10, 3, 5, 9, 2};

	private static void insertionSort(int[] data, int length) {
		for(int i=1; i<length; i++) { //key는 두번째 원소에서 시작
			for(int j=i; j>0; j--) { //연속된 두 원소의 크기를 비교하여 정렬하는 루프
				if(data[j] < data[j-1]) {
					int temp = data[j];
					data[j] = data[j-1];
					data[j-1] = temp;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		insertionSort(data, data.length);
		for(int a : data) {
			System.out.print(a + " ");
		}
	}
}

 

🕊참고자료

[알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog