선택정렬 (Selection Sort)

한유진·2021년 10월 23일
0

알고리즘

목록 보기
1/8

정의


  • 리스트에 원소를 넣을 위치를 정해두고, 어떤 원소를 넣을지 선택하는 알고리즘
  • 거품 정렬 (Bubble sort)과 유사
  • 제자리 정렬 알고리즘 : 정렬되지 않은 값들 이외에 다른 추가 메모리를 요구하지 않는 정렬알고리즘 & 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택함
  • 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택함

과정 (내림차순)


  1. 리스트에서 최소값인 요소를 찾는다
  2. 최소값을 맨 앞의 요소와 교체
  3. 맨 앞의 요소를 제외하고 같은 과정을 반복

코드

void selectionSort(int[] A, int n)
{
	int indexMin, temp;
    for(int i = 0; i < A.length - 1; i++) {
    	indexMin = i;
        for (int j = i + 1; j < A.length; j++) {
        	if (A[j] < A[indexMin]) {
            	indexMin = j;
            }
        }
        temp = A[indexMin];
        A[indexMin] = A[i];
        A[i] = temp;
 	}
}           

시간복잡도

  • 비교 횟수
  • 최악, 평균, 최선 모두 : (n - 1) + (n - 2) + ... + 3 + 2 + 1 = n(n-1) / 2
  • 교환 횟수
  • 회당 한 번 씩 : n - 1 # T(n) = O(n ^ 2)
  • 매개변수가 정렬이 되었는지와 상관없이 무조건 비교하므로 최악, 평균, 최선 모두 동일

출처

https://devuna.tistory.com/28

profile
열정열정

0개의 댓글