[알고리즘] 선택 정렬(Selection Sort)

 

 

해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 정렬 알고리즘

• 입력 배열 이외에 다른 추가 메모리를 요구하지 않는다. (in-place sorting)
• 첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다.
• 두 번째 순서에는 두 번째 위치에 남은 값 중에서의 최솟값을 넣는다.
• ...

 

 

🔘  과정

---

1. 주어진 배열 중 최솟값 찾기
2. 해당 값을 맨 앞에 위치한 값과 교체
3. 나머지 배열을 같은 방법으로 교체

 

🔘  코드(c++)

 

void SelectionSort(int arr[]){
	int min;
	for(int i=0; i<arr.length-1; i++){
		min = i;
		for(int j=i+1; j<arr.length; j++){
			if(arr[j] < arr[min]) min = j;     //min값 업데이트
		}
	}
	swap(arr[min], arr[i]);                //swap
}

 

 

🔘 시간 복잡도

---

• 외부 루프 → n-1번
• 내부 루프 → n번
• O(n^2)

 

🔘 공간 복잡도

---

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)이다.

 

 

🔘 장점

---

• 자료 이동 횟수가 미리 결정
• 정렬을 위한 비교 횟수는 많지만, bubble sort에 비해 실제 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 상태에서 비교적 효율적
• 제자리 정렬(in-place sorting)

 

 

🔘 단점

---

• 불안정 정렬(Unstable Sort)

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!

 

 

 

 

 

참고: https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html