선택정렬 알고리즘 typescript

TOC

1. 문제

2. 제공 함수

3. 선택정렬

4. 시간복잡도

문제

1 2 5 7 3 0 9 10을 오름차순으로 정렬하세요.

제공 함수

우선 JS의 기본 제공 함수를 사용해서 정렬을 해보자.

const arr:number[]=[1,2,0,2,9,8,12,13,11];
function ascending(params:number[]):number[] {
	const answer:number[]=arr.sort((a,b)=>{return a-b})
	console.log(answer)
	return answer;
}

ascending(arr);

[
  0,  1,  2,  2, 8,
  9, 11, 12, 13
]

이미 잘 구축되어 있는 함수를 가져다 쓰는 것이기에 어디에서든 동일하게 작동하며 에러 걱정도 없다.

하지만 직접 구현함으로써 알고리즘 공부를 해보자.

선택 정렬 알고리즘

선택정렬 알고리즘은 아래의 규칙을 따른다.

주어진 리스트 중에 최소값을 찾는다.
그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. -위키피디아-

다른 사람들은 쉽다쉽다 하는데 그렇게 쉽지만은 않다.

이중 for문을 통해 배열을 순회한다.

포인트는 이중 for문이다.

0. 가장 낮은 값을 가리키는 인덱스를 minIdx라 하자.

1. 배열의 0 번째를 minIdx가 초기에 가리키게 한다.

2. i 번째는 고정시켜놓고 배열 중 가장 낮은 값을 순회하며 찾는다. (이중 for 문)

3. 2번의 조건에 만족할 경우 minIdx의 값을 변경한다 (j로 순회중이므로 j로 변경)
   (minIdx는 배열의 값을 순회하다 0 번째 배열의 값보다 낮은 값을 만나 minIdx가 변경됨)

4. 4.1 스왑을 위해 현재 찾은 값 중 가장 낮은 값을 temp에 임시 저장한다.
   4.2 찾아낸 작은 값의 위치는 0 < minIdx 이므로 배열상 위치는 예를 들면 [2][0]라는 배열에서 1 번째 배열에 속한다. 따라서 1 번 배열방에 i 번째 값을 저장한다.
   4.3 [2][0]에서 i 번째는 아직 정렬되지 않은 맨 앞자리이므로 i 번째에 찾은 값인 ary[minIdx]를 넣어준다.

5. 만약 [0][2]로 정렬되어 있다면
   minIdx는 여전히 0 번째 배열을 가리키고 있으므로 temp=0, ary[minIdx]=0 === ary[0]=ary[0], ary[i]=temp를 저장한다. 변경되는 것이 없다.

function ascending1(parm:number[]):number[]{
	let ary=parm; 
	for(let i=0;i<parm.length-1;i++){ // 2
		let minIdx:number=i; // 0, 1
		for(let j=i+1;j<parm.length;j++){ // 2
			if(ary[minIdx]>ary[j]){ // 3
				minIdx=j;
			}
			let temp=ary[minIdx]; // 4.1
			ary[minIdx]=ary[i]; // 4.2
			ary[i]=temp; // 4.3

		}
	}
		console.log(ary);
	return ary;

}

4. 시간복잡도

선택정렬의 시간복잡도는 이중 for문을 전부 돌아야 결과가 나오므로 $O(n^2)$의 시간복잡도를 가진다.

function ascending1(parm:number[]):number[]{
	let ary=parm; // 1
	for(let i=0;i<parm.length-1;i++){ // n
		let minIdx:number=i; // n
		for(let j=i+1;j<parm.length;j++){ // (n-1)n
			if(ary[minIdx]>ary[j]){ // (n-1)^2
				minIdx=j;
			}
			let temp=ary[minIdx]; // (n-1)^2
			ary[minIdx]=ary[i]; // (n-1)^2
			ary[i]=temp; // (n-1)^2
			// 1+n+n+n(n-1)+4(n-1)^2 = n+n^2+n^2-2n-4 = 5n^2-7n+5 -> O(n^2)

		}
	}
	return ary;

}

상수를 모두 없애고 가장 영향이 큰 최고차항을 가져와 시간복잡도를 계산해 보면 최대 $O(n^2)$의 시간이 걸린 후 결과를 반환합니다.

실제 서비스에서 사용할만한 알고리즘은 아니죠