Exchange Sort

1. Problem

- n개의 요소를 오름차순으로 정렬해보자.

 

2. Input

1) 양수 n

2) 배열 S indexed from 1 to n

 

3. Output

1) 오름차순으로 정렬된 S

 

4. PseudoCode

void exchangesort(int n, keytype[] S){
    index i, j;
    for(i=1 ; i<=n ; i++)
        for(j=i+1 ; j<=n ; j++)
            if(S[j]<S[i])
                exchange S[i] and S[j]
}

 

5. Example

class Test {
    public static void main(String[] args){
    	int[] arr = {3, 6, 2, 1, 0};
    	exchangesort(arr.length, arr);
    	for(int i : arr)
    		System.out.print(i); // 01236
    	
    }
    
    static void exchangesort(int n, int[] S){
    	for(int i=0 ; i<n ; i++) {
    		for(int j=i+1 ; j<n ; j++) {
    			if(S[j]<S[i]) {
    				int tmp = S[j];
    				S[j] = S[i];
    				S[i] = tmp;
    			}
    		} // j
    	} // i
    }
}

- T(n) = n*(n-1)/2