선택정렬 (Selection Sort)

선택정렬이란 배열에서 가장 작은 숫자를 맨 앞으로 보내는것이다.

#include <stdio.h>

int main(void) {
	int arr[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    int i, j, temp, min, index;
    
    for(i=0; i<10; i++){
    	min = 100;	// 배열에 있는 가장 큰 수보다 더 크게만 하면 됨
        for(j=i; j<10; j++){
        	if(min > arr[j]){
            	min = arr[j];
                index = j;
            }
        }
        temp = arr[i];			// 스와핑
        arr[i] = arr[index];
        arr[index] = temp;
    }
    
    for(i=0; i<10; i++){
    	printf("%d ", arr[i]);
    }
    return 0;
}

가장 직관적이고 이해하기 쉽지만 시간복잡도는 N * (N + 1)/2 이며 O(N^2)라고 한다.

 

자바

public class SelectionSort {
    public static void main(String[] args) {
        int[] array = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        int temp, i, j;
        int index=0;

        for(i=0; i<array.length; i++){
            int min=100;
            for(j=i; j<array.length; j++){
                if(min > array[j]){
                    min = array[j];
                    index = j;
                }
            }
            temp = array[i];
            array[i] = array[index];
            array[index] = temp;
        }
        for(i=0; i<array.length; i++){
            System.out.println(array[i]);
        }

    }
}