Algorithm

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

Juliie 2020. 4. 13. 02:26

선택 정렬(selection sort)

전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬

 

수행 방법

  1. 각 루프마다 최소 원소를 찾는다
  2. 최소 원소와 맨 왼쪽 원소를 교환한다
  3. 맨 왼쪽 원소를 제외한다
  4. 하나의 원소만 남을 때까지 위의 루프를 반복

선택 정렬이 진행되는 과정

 

 

수행 시간: O(n2)

• for 루프는 n-1번 반복

가장 큰(또는 작은) 수를 찾기 위한 비교횟수: n(n-1)/2

숫자 사이의 자리 교환은 상수 시간 작업

 

특성

모든 입력에 대해 동일한 θ(n^2) 알고리즘

 입력 크기가 작고 요소들간의 교환 비용이  경우 적절한 알고리즘

 

코드 구현

더보기
public class Sort { //최댓값을 오른쪽으로
	public void selectionSort(int[] a) {
		int i, j, maxNum, maxIndex;

		for (i = a.length-1; i >= 0; i--) {
			maxNum = a[i];
			maxIndex = i;
			for (j = 0; j < i; j++) {
				if (a[j] > maxNum) {
					maxNum = a[j];
					maxIndex = j;
				}
			}
			if (a[i] < maxNum)
				swap(a, maxIndex, i);
		}
	}

	public void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	public void printArray(int[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}
}
public class Sort { // 최솟값을 왼쪽으로
	public void selectionSort(int[] a) {
		int i, j, minNum, minIndex;

		for (i = 0; i < a.length; i++) {
			minNum = a[i];
			minIndex = i;
			for (j = a.length - 1; j > i; j--) {
				if (a[j] < minNum) {
					minNum = a[j];
					minIndex = j;
				}
			}
			if (a[i] > minNum)
				swap(a, minIndex, i);
		}
	}

	public void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	public void printArray(int[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}
}

 

1 2 3