[자바] 정렬의 종류와 알고리즘 (선택정렬) 간단 예제.

[자바] 정렬의 종류와 알고리즘 (선택정렬) 간단 예제.

정렬에는 여러가지 종류가 있다.

우선 선택 정렬.

(5,6,4,3,1,6,2) 이렇게 존재 한다고 가정했을 때.
가장 작은 숫자를 찾는다. (1) 이를 첫번째 자리의 숫자과 교체한다.
일반적으로 교체하는 알고리즘(?)이 굉장히 많이 쓰이는데 잠깐 알아보도록 하자.

1. 임의의 변수를 하나 만들고 그 안에 교체될 대상의 값을 저장한다. [temp = 5]
2. 교체될 대상에 선택한 값을 덮어 씌운다. [5에 1을 덮어 쓴다.]
3. 그러면 5라는 값은 사라지고 1 이 2개가 되었을 것이다. (1,6,4,3,1,6,2)
4. 여기서 선택했던 1에 temp의 값을 덮어 씌운다.(대입) [1 = temp]
5. temp는 5가 들어 있었으므로 배열에는 [1,6,4,3,5,6,2,] 로 변경 된다.

위의 내용을 코드로 바꾸자면 아래와 같다. ( arr 이라는 배열에 담았다고 가정. )

temp = arr[0];
arr[0] = arr[4];
arr[4] = temp ; 

지금은 숫자로 사용했지만 주로 반복문에서 많이 사용하기 때문에 i 처럼 변수를 사용한다.

 

아주 간단한 예로.
우선 첫번째 for문은 랜덤함수를 이용한 배열의 초기화.
일일이 값을 넣어 초기화 하기 귀찮으니 랜덤함수를 사용해서 초기화를 해 주었음.

랜덤함수의 사용법을 모른다면 아래 링크를 참조.
2011/04/06 - [프로그래밍./Java] - [자바]Math.random() 함수 이해하기.

두번째 for문은 배열의 값을들 출력하기 위한 반복문으로
일반적인 for문과는 조금 다른 for each문. 다른 연산없이 순수하게 배열의 모든 값을 연산할 때 필수

이 역시도 for each 문을 사용할 줄 모른다면 아래 링크를 참조.
2011/04/11 - [프로그래밍./Java] - [자바] for each문 사용법.




세번째 for문이 정렬을 하는 부분인데. 

배열의 첫번째를 선택해서(last = i ) 그 다음 요소들과 비교를 해 나간다. (j = i + 1)

첫번째를 기준으로 한칸씩 넘어가면서 비교를 하다가 작으면 그 요소를 선택 (last = j)

배열의 끝까지 확인 한 후 사실상 가장 작은 숫자를 가지고 있는데 그것을 첫번째 요소와 교체한다.

위에서 설명한 temp를 이용한 교체.

다음은 i가 하나 올라가서 2번째 요소가 기준. 2번째 보다 하나 큰 요소들부터 다시 검사.

위와 같은 내용이 반복 되는 것이다.


이래도 이해가 잘 되지 않는다면
 종이에 5개 정도의 칸을 그려서 직접 임의의 숫자를 넣고
칸 위에 배열의 주소(0,1,2,3,4) 써 놓고
위의 알고리즘대로 한번씩 차례대로 해보면 이해가 될 듯.






사실 조금 더 깊게 이야기를 하자면
 위의 세번째 for문에서 i < list.length 로 조건문을 사용했습니다.
하지만 실제로는 list.lenght-1 하는게 맞습니다.
 결과는 같지만 마지막에 1번은 무의미 하기 때문이죠.

크기가 5인 a배열이 있다고 가정한다면

a[0]번을 기준으로 검사.
a[1]번을 기준으로 검사.
a[2]번을 기준으로 검사.
a[3]번을 기준으로 검사.

a[3]번 즉, 4번째를 검사하고 교체 했다면

4번째와 5번째를 비교해서 작은 수는 a[3]번에, 큰 수는 a[4]번에 넣었겠죠?

그렇다면 이미 정렬이 끝난 상태입니다.

가장 마지막인 a[4]을 기준으로 검사를 할 다음 배열이 없는 거죠.

저 위에 그림으로 비교를 하자면. list의 크기는 10이고
for( i = 0; i < list.length; i++ )로 해서.
0 ~ 9 까지 총 10번을 하게 되어 있지만

아래를 보면
for ( j = i+1 ; j < list.length; j++ ) 로 되어 있습니다.
i가 9인 경우 j 는 10 이되고 list.length 랑 같아서 반복문을 빠져나오게 됩니다.

따라서 사실상 실제적으로 반복하는 횟수는 0~8까지 총 9번이 되는거죠.
즉, i < list.length - 1 까지만 반복을 실행하는 겁니다.

조건식에 의해서 알아서 빠져나와 결과 값이나 처리에 이상은 없지만
무의미한 1번의 검사를 더 하게 되는 것이죠.



유용한 정보가 되셨다면 아래 손가락 버튼 한번 눌러주세요 ^-^