선택정렬, 버블정렬, 삽입정렬

1. 개요

1) 선택정렬

가장 간단한 정렬방법입니다.

6 3 4 5 1 2 리스트 중에서

최소값을 찾아 맨 앞에 위치시킵니다.

1 6 3 4 5 2

그리고 나머지 원소 중에서 다시 최소값을 찾습니다.

1 2 6 3 4 5

이를 n번 반복하면 

1 2 3 6 4 5

1 2 3 4 6 5

1 2 3 4 5 6

정렬된 리스트를 얻을 수 있습니다.

 

2) 버블정렬

오른쪽 끝에서부터 최소값(왼쪽에서 시작할 경우는 최대값)을 거품이 올라오듯 보글보글 불러오는 방법입니다. 

인접한 두 개 원소를 비교해서 작은 값을 땡겨오고 또 옆에 있는 놈과 비교해서 땡겨오고 하다보면

최소값이 리스트 시작점에 쌓이게됩니다.

 

3) 삽입정렬

길이가 1인 정렬된 리스트에 원소를 하나씩 추가하여 정렬된 리스트의 길이가 n이 되면 종료합니다.

 

2. 구현

1)

public class SelectionSort {

	public void sort(Integer[] arr){
		
		Scanner sc = new Scanner(System.in);
		Tools t = Tools.createTools();
		
		int n = arr.length;
				
		for(int j = 0; j < n; j++) {
			int minId = j;
			for(int k = j+1; k < n; k++) {
				if(arr[k] < arr[minId]) {
					t.swap(arr, minId, k);
				}
			}
			arr[j] = arr[minId];
		}
		
		
	}
}

2)

public class BubbleSort {
	
	
	public static void sort(Integer[] arr) {
		
		Tools t = Tools.createTools();
		
		for(int i = 0; i < arr.length; i ++) {
			for(int j = arr.length-1; j > i; j--) {
				if(arr[j] < arr[j-1]) t.swap(arr, j-1, j);
			}
		}
	}	
}

 

3)

public class InsertionSort {
	public static Integer[] sort(Integer[] arr) {
		Integer[] sorted = new Integer[arr.length];
		sorted[0] = arr[0];
		
		for(int j = 1; j < arr.length; j++) {
			int i = j-1; 
			while(i > -1 && arr[j] < sorted[i]) i--;
			insert(sorted, j, i, arr[j]);
		}
		return sorted;
	}
	
	public static void insert(Integer[] ar, int slen, int index, int value) {
		
		for(int i = slen-1; i > index; i--) {
			ar[i+1] = ar[i];
		}
		ar[index+1] = value;
	}
}

 

3. 평가

• 세 가지 방법 모두 평균적으로 O(n²) 시간이 소요됩니다.
• 선택정렬의 경우 최소값을 찾기 위해 리스트의 끝까지 탐색을 수행하므로 stable* 하지 않습니다.

* 안정성 : 중복값이 있을 때 정렬 전 리스트의 순서가 유지되는 경우 안정적이라고 합니다.

즉 3 1 1 4 2 를 정렬하면 1 1 2 3 4 가 나올 때 안정적인 정렬 방법입니다.

하지만 선택정렬은 1 1 2 3 4 가 되므로 안정적이지 않습니다. 

• 앞의 두 가지 방법이 초기 리스트 상태와 관계없이 같은 시간이 걸리는 반면,
• 삽입정렬의 경우 정렬할 리스트의 상태에 따라 수행 시간이 달라집니다.

최적의 경우는 정렬된 리스트입니다. 삽입시 O(1) 시간이 소요되므로 총 O(n)

최악의 경우는 역순으로 정렬된 리스트입니다. 삽입시 O(n) 시간이 소요되므로 총 O(n²) 

• 버블정렬의 경우 1회 수행시 한번도 swap을 하지 않았다면, 즉 리스트가 이미 정렬된 상태라면 도중에 종료시킴으로써 시간을 단축시킬 수 있습니다.
• 삽입정렬시 이진탐색을 이용할 경우 비교 연산에 필요한 시간을 단축할 수 있습니다.
• 배열 대신 연결리스트로 구현할 경우 레코드이동에 필요한 시간을 단축시킬 수 있습니다.

	비교연산	레코드이동
이원 삽입정렬	O(nlogn)	O(n²)
연결 삽입정렬	O(n²)	O(nlogn)