배열과 정렬

배열과 정렬

• A라는 배열과, A가 정렬된 B라는 배열은 순서는 서로 다르지만 집합적으로는 같은 집합이다
• B의 첫 번째 원소는 A에서 가장 작은 원소, B의 두 번째 원소는 A에서 두 번째로 작은 원소...

선택정렬

• A의 가장 작은 원소를 맨 앞 원소와 서로 자리를 바꾼다
• 맨 앞 원소를 제외한 범위에서 A의 가장 작은 원소를 맨 앞 원소와 서로 자리를 바꾼다
• 마지막 바로 앞까지 반복한다 (어차피 마지막은 의미 없기 때문)

public void selectionSort(int[] data) {
    for (int i = 0; i < data.length - 1; i++) {
    	// 주어진 범위에서 가장 작은 원소의 index
    	int indexOfMin = getIndexOfMinInRange(data, i, data.length - 2);
        elementSwap(data, i, indexOfMin);
    }
}

private void getIndexOfMinInRange(int[] data, int start, int end) {
    int indexOfMin = data[start];
    for (int i = start; i <= end; i++) {
        if (data[i] < data[indexOfMin]) {
            indexOfMin = i;
        }
    }
    
    return indexOfMin;
}

private void elementSwap(int[] data, int source, int target) {
    int temp = data[source];
    data[source] = data[target];
    data[target] = temp;
}