선택정렬 알고리즘

선택정렬 알고리즘

package com.example.demo.selectionSort; public class SelectionSort { public static void swapElements(int[] array, int i, int j) { int temp = array[i]; array[i]  = array[j]; array[j] = temp; } public static int indexLowest(int[] array, int start) { int lowIndex = start; for(int i = start; i <array.length; i++) { if(array[i] < array[lowIndex]) { lowIndex = i; } } return  lowIndex; } public static void selectionSort(int[] array) { for(int i =0; i <array.length; i++) { int j = indexLowest(array, i); swapElements(array, i, j); } } public static void main(String[] args) { int testArray[] = {1,6,3,2,4,5}; selectionSort(testArray); for(int i : testArray){ System.out.println(i); } } }

설명

swapElements는 배열에 있는 두 요소의 값을 바꾼다.

요소를 읽고 쓰는 것은 상수 시간 연산

요소의 크기와 첫 번째 위치를 알고 있다면 한번의 곱셈과 덧셈으로 어떤 요소의 위치라도 알 수 있기 때문이다.

indexLowest는 주어진 위치인 start에서 시작해서 배열에 있는 가장 작은 요소의 인덱스를 찾는다.

반복문을 돌때마다 배열의 두 요소에 접근하고 한번의 비교 연산을 한다.

이들은 모두 상수 시간 연산이므로 어느 것을 세든지 중요하지 않다.

비교횟수를 센다.

1. start 인자가 0이면 indexLowest 메서드는 전체 배열을 검색하고 전체 비교 횟수는 배열의 길이인 n이 된다.

2. start 인자가 1이면 비교 횟수는 n-1이다

3. 일반적으로 비교회수는 n-start가 되어 indexLowest 메서드는 선형이된다

selectionSort는 배열을 정렬한다.

0에서 n-1까지 반복하므로 n번 반복 실행한다.

매번 indexLowest 메서드를 호출한 후 상수 시간 연산인 swapElements 메서드를 실행한다.

indexLowest 메서드가 처음 호출되면 n번 비교 연산을 한다.

두번째는 n-1번 비교 연산을 한다.

총 비교 회수는 n + n-1 + n-2 + ... + 1 + 0 이다

이 수열의 합은 n(n+1)/2 이고 n^2에 비례한다.

이차를 의미한다.