[선택정렬] Python, Java, Kotlin

상단의 이미지와 같이 앞에 값 하나와 그 이외의 값의 크기를 계속 비교하면서 최소값을 찾아나간다.

시간 복잡도는 N번만큼 가장 작은 수를 가장 앞으로 보내야한다. 처음 0번째 부터 하나씩 오른쪽으로 밀려가는 for문이 돌아가므로 N+(N-1)+(N-2)+...+2 이고 마지막은 굳이 정렬을 돌리지 않아도 된다. 등차수열의 합 공식 n(a+l)/2 = (N-1)(N+2)/2 = (N^2+2N-N-2)/2 = (N^2+N-2)/2 가 된다 빅오 표기법에 의해 가장 큰 N^2만 남게되고 O(N^2)가 된다.

 

- Python

# 파이썬
array=[7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

#selection sort
for i in range(len(array)):    
    tempIdx=i
    for j in range(i+1,len(array)): 
        if array[tempIdx] > array[j] :
            tempIdx=j
    array[i],array[tempIdx] = array[tempIdx],array[i]

print(array)

 

- Java

// 자바
public class Main_SelectionSort {
    public static void main(String[] args) {
        int[] array={7,5,9,0,3,1,6,2,4,8};
        int tempIdx=0;
        StringBuffer sf= new StringBuffer();
        for(int i =0 ; i< array.length;i++){
            tempIdx=i;
            for (int j=i+1;j< array.length;j++){
                if(array[tempIdx]>array[j]){
                    tempIdx=j;
                }
                int temp=array[i];
                array[i]=array[tempIdx];
                array[tempIdx] = temp;
            }
        }
        for (int i=0;i< array.length;i++) {
            sf.append(array[i]);
            if(i < array.length-1){
                sf.append(", ");
            }
        }
        System.out.println(sf.toString());
    }
}

 

- Kotlin

//코틀린
fun main(array:Array<String>){
    var array = arrayOf<Int>(7,5,9,0,3,1,6,2,4,8)
    var tempIdx:Int=0
    for (i in 0 until array.size){
        tempIdx=i
        for (j in i+1 until array.size){
            if (array[tempIdx] > array[j]){
                tempIdx = j
            }
            var temp:Int=array[tempIdx]
            array[tempIdx]=array[i]
            array[i]=temp
        }
    }

    for (i in 0 until array.size){
        print(i)
        if( i < array.size-1){
            print(", ")
        }
    }
}