[자바] 선택정렬(Selection Sort) 코드. 시간복잡도

public class SelectionSort {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		System.out.println("정렬할 수 10개를 입력하세요 : ");
		Scanner input = new Scanner(System.in);
		
		int[] data = new int[10];
		
		for(int i = 0; i < data.length; i++) {
			data[i] = input.nextInt();
		}
		
		long start = System.nanoTime();
		
		maxSelectionSort(data);
		
		System.out.print("\n\n정렬 결과는 : ");
		
		for(int i = 0; i < data.length; i++) {
			System.out.print(data[i] + " ");
		}
		
		long end = System.nanoTime();
		System.out.println("\n실행 시간 : " + ( end - start )/100000000.0); 
		
	}
	
	// 1. 작은 수부터 비교하는 코드
	public static void minSelectionSort(int[] A) {
		
		for(int i = 0; i < A.length - 1; i++) {
			
			int min = i;
			
			for(int j = i + 1; j < A.length; j++) {
				if(A[min] > A[j])
					min = j;
			}
			
			int temp = A[i];
			A[i] = A[min];
			A[min] = temp;
		}
		
	}
	
	// 2. 큰 수부터 비교하는 코드
	public static void maxSelectionSort(int[] A) {
		
		for(int last = A.length - 1; last > 0; last--) { 
		// 마지막 인덱스 값을 last로 두고 1까지 1씩 줄어든다.
			
			int max = last;
			
			// A[0...last] 중 가장 큰 수 A[max]를 찾는다.
			// last가 줄어들면서 비교
			for(int j = last - 1; j >= 0; j--) {
				if(A[max] < A[j])
					max = j;
			}
			
			// A[max]랑 A[last]랑 교환하여 맨 마지막에 큰 값을 보낸다.
			// 큰 수를 끝쪽으로 보내고 비교 변수를 1씩 줄어들게 하면서 끝으로 보낸 값을 고정시킨다.
			int temp = A[last];
			A[last] = A[max];
			A[max] = temp;
		}
		
	}

 

 

# 선택정렬 알고리즘

 

1) A[0...last] 중 가장 큰 수 A[max]를 찾는다.

2) A[max] 와 A[last] 값을 교환한다.

 

 

 

#

1) 제일 큰 수 찾아

2) 맨 마지막을 last라고 둬

3) 제일 큰 수랑 last랑 교환

4) last-1번 반복

 

 

 

# 실행시간

O(n2)​

> 외부 for 루프 : n-1 번 반복

> 가장 큰 수 찾는 내부 for 루프 : n-1번, n-2번...2번, 1번 반복

> 교환은 상수 시간 작업

 

따라서

T(n) = (n−1)+(n−2)+...+2+1​

      = n(n−1)2​​

      = O(n2)​