선택 정렬

하 요새 ㅠㅠ 몸도 아프고 친형의 결혼식 덕분에 인생에서 가장 바빴던 2주였던것 같다. ㅠㅠ 앞으로도 이렇게 바쁠 날이 있을텐데 아무리 바쁘더라도 내 블로그를 방치하지 말자 ㅠㅠ 내 보물

내가 생각하기에 정렬은 알고리즘 중에 가장 흔하고 접할 일이 많다고 생각한다. 자바를 조금 더 공부하다 보면 정렬을 도와주는 다양한 메서드들을 만날 것이다.
하지만 내가 말하고 싶은 것은 자바에서 제공해주는 다양한 기능들에 익숙해지지 말자는 것이다.
물론 더욱 깔끔하고 가독성 좋은 코드를 쓰기 위해선 메소드를 씀으로써 코드를 짧고 이해하기 쉽게 만드는 것도 중요하지만 정렬의 원리를 모른다면 제대로 된 응용을 할 줄 모르게 될 것이다.

자 그럼 시작해보자!!

선택 정렬
가장 작은 숫자를 찾아 앞으로 보내는 방식으로 앞에서 뒤로 쭉 비교해 나가며
큰 숫자가 있으면 앞으로 보내는 방식을 반복한다.

순서
1. 주어진 리스트 중에서 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다
3. 맨 처음 위치를 뺀 나머지 리스트들을 반복 교체한다.

위에서 적은 순서를 생각하며 그림을 보면 제일 작은 값이 반복해서 제일 앞으로 교체되는 것을 볼 수 있을 것이다.

우리는 위 그림과 같이 코드를 알고리즘으로 구현하면 된다.

1. int[] arr = new int[10];
		
    for(int i = 0; i < arr.length;i++){
		arr[i] = (int)(Math.random() * 100) + 1;      
		}

for(int i = 0; i < arr.length - 1; i++){
2. int min = i;  // i = 첫번째 값이 들어있는 위치    i부터 저장한다. 
	for(int j = i + 1; j < arr.length; j++){
3.		 if(arr[j] < arr[min]){
4.			min = j;                
				}		
			}
5.			int temp = arr[i];              
6.			arr[i] = arr[min];
7.			arr[min] = temp;      
		}
8.       System.out.println(Arrays.toString(arr));

위에서 부터 아래 순서로 코드에 대한 설명을 시작하면,

1. 배열의 크기가 10인 int타입 arr배열에 1 부터 100까지의 난수를 저장한다.
2. int min = i; 의 뜻은 첫 비교시에 가장 작은 수는 무조건 첫 번째 수이기 때문이다.
3. if(arr[j] < arr[min]) 첫 번째 값과 리스트의 모든 수와 비교 후
4. 가장 작았던 j번째 인덱스를 min 변수에 저장한다.
5. 값을 잠시 보관해줄 temp라는 변수를 선언 후 비교 대상이었던 i번째의 인덱스에 있던 수를 저장한다.
6. 그 후 i 번째 인덱스에는 최소값 min 인덱스의 수를 넣어준다.
7. min 인덱스 자리가 빠졌기 때문에 그 자리에는 i번째 인덱스의 값을 넣어준다.
8. 위 방법을 반복하여 min은 계속해서 앞으로 이동하고 i는 뒤로 이동하며 오름차순 정렬된다.

min 때문에 어려워 보일 수 있는데 쉽게 생각해서 min은 i 이면서 j 이다.
이차 for문 안에서는 i로 사용되고 바깥에서는 j로 사용된다.
그 이유는 j는 이차 for문 안에서만 사용할 수 있기 때문에 따로 변수에 저장하여 밖으로 빼준것이다.

다음은 버블 정렬이다. ㅎㅎ