<선택 정렬 & 삽입 정렬>

두 정렬 모두 시간복잡도가 o(n^2)라 느리긴 하지만, 배워두면 쓸데가 있지 않을까 하고 포스팅해본다.

 

 

배열은 9 2 4 5 3 . 크기 5짜리라고 가정하자

 

1. 선택정렬

선택정렬의 컨셉은 간단히 말하면  최솟값을 0번째 인덱스에 집어 넣는다 생각해야한다.

 첫번째 loop부터 살펴보자. i=0 & j = 1,2,3,4

i=0일때, minindex=0이겠다. 여기서 j=1,2,3,4로 움직이면서 첫번째 인덱스보다 다음인덱스가 작다면 minindex를 초기화하고 이를 j = 1,2,3,4 다 돌면 최종적으로 최소값을 지닌 인덱스가 나올 것이다.

minindex = 1이라는 결론이 나오고. temp > arr[1] , arr[1] > arr[0] , arr[0] > temp( 즉 temp는 여기서 최솟값이겠다)

즉 첫번째 loop를 지나면 9 2 4 5 3 이었던 초기배열에서의 최솟값인 2가 첫번째 인덱스로 가면서  그 자리는 바뀜당했던 녀석이 채워서 배열의 상태는 그대로이게 설정하면 2 9 4 5 3이겠다. 

 

자 다음 loop

i=1일때, j = 2,3,4

이제 알겠다 ! 첫번째 loop를 통해 최신화된 배열 2 9 4 5 3에서 9 4 5 3이라는 배열에서의 최소값을 찾아

맨 앞에두고 temp로 값을 바꿔준다면 9 4 5 3이라는 부분배열중에서도 최소가 맨 첫 인덱스로가고 

 

이 loop를 반복하면 부분배열의 최소가 계속 맨 왼쪽으로 가기에 자연스레 정렬이 되는 메커니즘을 찍겠다.

 

public	static void selectionSort(int[] arr) {
		int n= arr.length;
		for(int i=0; i<n-1; i++) {
			int minindex = i;
			for(int j=i+1; j<n; j++) {
				if(arr[j] <arr[minindex]) {
					minindex = j;
				}
			}	
			int temp = arr[minindex];
			arr[minindex] = arr[i];
			arr[i] = temp;
		}
		
	}

 

 

 

2.삽입 정렬

public static void insertionSort(int[] arr) {
		int len = arr.length;
		for(int i=1; i<len; i++) {
			int key = arr[i];
			int j=i-1;
			while(j>=0 && arr[j] > key) {
				arr[j+1] = arr[j];
				j=j-1;
			}
			arr[j+1] = key;
		}
		
	}

 

배열은 음 2 4 9 5 3 으로 가정하자.

삽입 정렬은 j라는 변수가 상당히 큰 역할을 한다.

 

첫번째 loop i =1. j =-0.

삽입 정렬은 key라는 초기값을 설정하여 이 key라는 값은 자연스레 왼쪽 인덱스와 비교할수 있게 j = i-1으로 설정하고, 

여기서 key = 4겠다.

자 while로 들어갈 조건을 보자, j 0 이상이며 arr[0] 이 key보다 클때 while로 들어가서 arr[1], 즉 key의 자리에는 값이 arr[0]으로 바뀌며 j값이 하나 준다. 

하지만 arr[0] 이 key보다 작기에 다음 loop.

 

두번째 i=2. j=1

key = 9

똑같이 무시하겠다. key가 더 크니까

 

세번째 i=3. j=2

key = 5

여기선 문제가 발생한다 while로 들어가서 arr[3] = arr[2]가 되며 j=1이 된다. > .2 4 9 9 3.

아래에서 arr[2] =key니까 현재 배열 상태는  > 2 4 5 9 3.

자 현재 j =1 이기에 while문으로 들어갈 자격을 검사해보자 arr[1] >key 인가?

아니다. 따라서 다음 loop로

 

마지막 i=4 j=3

key =3

key가 더 작으니 while로 들어가야하고, arr[4] =arr[3] > 24599

j=2

arr[j+1} = key이니까 24539.

 

다시 while loop로

j=2이며 key는 그대로 3이다. key가 arr[2]보다 작다.   (3<5)

 

따라서 while로 들어가

arr[3] = arr[2] > 24559 and j=1.

arr{j+1] = key니까

arr[2] = 3 >> 24359

 

다시 while문으로! 

arr[2] = arr[1]  . 24459.

j =0 이됬고

arr[j+1] =key니까

23459로 최신화된다.

 

이제 while문 체크 해보자. j는 0보다 크거나 같다. 하지만 key가 더 크다!!

 

따라서 마지막 loop도 빠져나오고 정렬이 된 모습을 볼 수 가있다.

어떻게 보면 상당히 복잡하기도 한데  개인적으로 편한건 부등호 하나만 바꿔주면 작은 순서 or 큰 순서로 정렬 가능한게 좀 매력적이다.