JAVA 선택정렬 알고리즘을 이용한 랭킹구하기

선택 정렬 개념

선택 정렬(selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n²) 만큼의 시간이 걸린다. – 위키백과

그림으로 이해하기

• i를 0부터 length – 1까지 j(i + 1 부터 length까지)와 차례로 비교하기 (j =i + 1 부터 length까지)
• 버블정렬은 오른쪽부터 채워지는 반면, 선택정렬은 왼쪽부터 채워진다.

랭킹 구하기

• 먼저 모든 랭킹 요소의 값은 1로 초기화시킨다.
• 하나씩[i] 뒤의 수[j]와 비교하면서 더 작은 수의 랭킹 요소를 ++시킨다 (낮은 순위주기) (값이 같을 경우는 조건으로 만들지 않아도 됨)

//랭킹 초기화
    for(int i = 0; i < students_no; i++) {
        ranking[i] = 1;
    }
		
//랭킹 정렬(selection srot)
   for(int i = 0; i < students_no - 1; i++) {
        for(int j = i + 1; j < students_no; j++) {
            if(total[i] > total[j]) {
		ranking[j]++;
	} else if(total[i] < total[j]) {
		ranking[i]++;
	}
    }
}