[자료구조][JS] 선택 정렬(Selection Sort)

선택 정렬(Selection Sort)

• 시간 복잡도
  • 최선: O(n^2)
  • 최악: O(n^2)
  • 평균: O(n^2)

 

 

• 장점
  • 실행 전에 자료의 이동 횟수를 알 수 있음
  • 보조 메모리가 제한되는 경우 복잡한 알고리즘에 비해 성능적인 이점을 낼 수 있음
• 단점
  • 보통의 경우 O(n^2)의 시간 복잡도로, 비효율적인 정렬 방식
  • 배열 내에 동일한 값이 중복되어 있다면 상대적인 위치가 변경될 수 있음

- 코드 예시

function solution(arr) {
	let answer = arr;

	for (let i = 0; i < arr.length; i++) {
          let idx = i;
          for (let j = i + 1; j < arr.length; j++) {
              if (arr[idx] >= arr[j]) idx = j;
          }
          [arr[i], arr[idx]] = [arr[idx], arr[i]];
	}
	return answer;
}