JAVA 선택정렬(Selection Sort)와 삽입정렬(Insertion Sort)

배열안에 있는 숫자들이 규칙성을 갖지 않고 나열됐을 때 오름차순 또는 내림차순으로 정리하는 과정을 정렬이라고 한다.

 

코딩할 때 사용되는 대표적인 정렬 4가지가 있다.

 

1. 선택 정렬(Selection sort)

2. 삽입 정렬(Insertion Sort)

3. 병합 정렬(Merge Sort)

4. 퀵 정렬(Quick Sort)  

 

1. 선택 정렬(Selection sort)

 

1. 가장 첫 원소를 pivot으로 지정한다.

2. pivot의 우측 원소들중 가장 작은 원소와 대소관계를 비교한다.

3. pivot이 비교 원소보다 크다면 swap을 진행한다.

4. pivot값을 우측으로 한 칸 이동시킨다. 

 

 

 

public class Test019 {
	public static void swap(int arr[],int a, int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
	public static void main(String[] args) {
		int []arr = {1,9,4,7,6,5};
		
		//selection sort
		
		for(int i = 0; i < arr.length-1; i++) {
			int pivot = arr[i]; 
			int min = arr[i+1];
			int minIdx = i+1;
			for(int j = i+2; j < arr.length;j++) {
				if(min>arr[j]) {
					min = arr[j];
					minIdx = j;
				}
			}
			if(pivot>min) swap(arr,i,minIdx);
		}
		for(int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]); // 1 4 5 6 7 9
		}
	}
}

 

이중 for문을 통해 선택정렬을 구현했다.

 

바깥 for문은 배열의 첫째 원소부터 옆으로 한칸씩 pivot값을 이동시키는 역할을 한다.

 

안쪽의 for문은 pivot의 오른쪽 원소중 가장 작은 원소를 찾는 역할을 한다.

 

swap을 위해서 해당 원소의 index를 알아야 하기 때문에 가장 작은 원소의 index값을 저장하는 minIdx변수도 생성해야 한다.

 

2. 삽입 정렬(Insertion sort)

 

 

1. pivot의 왼쪽 원소들과 비교를 한다.

2. 비교하는 원소가 pivot보다 작은 원소라면 반복적으로 swap을 실행한다.

3. 비교하는 원소가 만약 pivot보다 큰 원소라면 swap을 멈추고 pivot을 다시 지정한다. 

 

배열의 첫번째 원소는 비교대상이 없기 때문에 두번째 원소부터 pivot을 지정해준다.

 

public class Test019 {
	public static void swap(int arr[],int a, int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
	public static void main(String[] args) {
		int []arr = {9,3,2,4,7,5};
		
		//insertion sort
		for(int i = 1; i < arr.length; i++) {
			int temp = i;
			for(int j = i-1; j >= 0; j--) {
				if(arr[j]>arr[temp]) {
					swap(arr,j,temp);
					temp = j;
				} else break;
			}
		}
		for(int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]); // 2 3 4 5 7 9
		}
	}
}

 

 

Insertion Sort또한 이중 for문으로 구현한다.

 

바깥쪽의 for문은 pivot을 지정하는 역할을 한다. (temp는 pivot의 index다.)

 

안쪽의 for문은 pivot 값과 비교해야 하기 때문에 초기값을 pivot의 index-1로 지정한다.

 

그러면 왼쪽의 원소부터 차례로 비교할 수 있다.

 

만약 swap이 발생하지 않는다면 break로 반복문을 종료시킨다.

 

 

 

두개의 정렬중 더 효율적인 알고리즘은 무엇일까?

 

여기서 시간 복잡도를 계산해야 한다.

 

1. 선택 정렬

		for(int i = 0; i < arr.length-1; i++) {
			int pivot = arr[i]; 
			int min = arr[i+1];
			int minIdx = i+1;
			for(int j = i+2; j < arr.length;j++) {
				if(min>arr[j]) {
					min = arr[j];
					minIdx = j;
				}
			}
			if(pivot>min) swap(arr,i,minIdx);
		}

 

바깥쪽 for문은 pivot을 이동하는 역할을 한다.

 

즉 어떠한 상황이던지 첫번째 원소부터 마지막 원소까지 이동을 해야한다.

 

따라서 배열의 길이가 N이라면 N번 이동해야한다.

 

안쪽 for문은 pivot이 N번 이동하면서 pivot의 우측값의 최소원소와 비교하는 역할을 한다.

 

만약 첫번째 원소가 pivot이라면 N-1개의 원소를 비교해야한다.

 

두번째 원소가 pivot이라면 N-2개

 

세번쨰 원소가 pivot이라면 N-3개

 

.....

 

따라서 총 N(N-1+N-2+N-3+...)번 이동을 해야 정렬알고리즘이 종료된다.

 

즉 N*(N/2) 대략적으로 O(N^2)의 시간복잡도를 갖는다.

 

1,2,3,4,5,6,7,8과 같이 정렬된 상태일지라도 pivot과 최소값을 비교해야하기 때문에

이동을 해야하는 횟수는 줄어들지 않는다. 

 

따라서 다음과 같은 시간 복잡도를 갖는다.

Best :  O(N^2)

worst : O(N^2)

 

 

2. 삽입 정렬

		//insertion sort
		for(int i = 1; i < arr.length; i++) {
			int temp = i;
			for(int j = i-1; j >= 0; j--) {
				if(arr[j]>arr[temp]) {
					swap(arr,j,temp);
					temp = j;
				} else break;
			}
		}

바깥쪽 for문은 선택 정렬과 같이 pivot을 이동시키는 역할을 한다. 따라서 N의 시간이 소요됨을 알 수 있다.

 

안쪽의 for문은 pivot의 좌측값과 비교하면서 swap을 진행하는 역할을 한다.

 

그렇다면 시간복잡도는 어떻게 될까?

 

최악의 경우

 

9,8,7,6,5,4,3,2,1

 

첫번째 pivot 8은 9와 swap한다.  - 8,9,7,6,4,3,2,1          1회

 

두번째 pivot 7는 9와 swap하고 8과 swap한다.  - 7,8,9,6,4,3,2,1     2회

 

세번째 pivot 6는 9와 swap하고 8과 swap하고 7과 swap한다.  - 7,8,9,6,4,3,2,1  3회

 

최악의 경우 N(1+2+3+4....) N^2의 시간복잡도를 갖는다. 선택 정렬과 유사한 복잡도를 갖는다.

 

최선의 경우

 

1,2,3,4,5,6,7,8

 

첫번째 pivot 2는 swap하지 않는다.

 

두번째 pivot 3는 swap하지 않는다.

 

세번째 pivot 4는 swap하지 않는다.

 

...

 

결국 pivot이 이동하는 N번의 시간만 소요되기 때문에 

 

최선의 경우 N의 시간복잡도를 갖는다.

 

따라서 다음과 같은 시간 복잡도를 갖는다.

Best :  O(N)

worst : O(N^2)

 

그나마 삽입정렬이 효율적인 알고리즘이라 할 수 있지만 현재 정리한 알고리즘은 직관적인 정렬알고리즘이다.

 

따라서 방대한 데이터를 정렬할 때 문제가 발생할 수 있다.

 

그러면 퀵 정렬과 병합 정렬은 더 효율적인 시간복잡도를 갖는지 정리해보자.