우선 For문에 대한 기본적인 이해가 있어야 이해할 수 있다.
시간복잡도가 빅오 표기법으로 O(N^2) (n제곱) 이라고 하는데 간단하게 말해서 무슨 소리냐면,
for문을 두번 돌아야 정렬이 끝난다는 소리다. (2중 for문으로 해결할 수 있다는 것이다)
2중 For문이 무엇인지도 모르는 생 기초 초보분도 있을 수 있으니 이해하기 쉽도록 쓰겠다.
이미 알고 있는 사람은 밑에 선택 정렬부터 보기를 바란다.
for(x=0 ; x<9 ; x++)
for(y=0 ; y<9 ; y++)
자 이걸 이해할 수 있는가? 있다면 이미 선택 정렬을 이해하는 것은 끝났다.
종이에 설명을 듣기 전에 먼저 써보라 어떤 식으로 진행될 거 같은가?
정답은
안에 있는 Y값이 먼저 증가된다.
0 - 1 - 2 - 3 - 4 - 5 - 6 -7 - 8
자 Y문이 한 번 끝났다.
그러면 이제 어떻게되는가?
X가 1 증가한다. 그리고 또 Y = 0 부터 ~8까지 Y를 1씩 늘려준다.
즉 Y가 0부터 8까지 계속 증가하는 행위를
X가 8이 될 때까지 반복한다는 얘기다.
X = 0 일때 Y는 0~8 , X = 1 되도 Y는 0~8 계속 반복하다가
X가 어? 이제 너 1을 더 증가시키면 9가 되는데? 그럼 너 x<9 이 조건안되잖아?
하면서 FOR문이 종료된다.
자 이제 선택정렬이다. 간단하다. 똑같이 2중 for문이다.
x(바깥쪽 for문 ) y (안쪽 for문)
5 4 3 2 1
->5와 4를 비교.
->5가 4보다 크니 바꿔준다.
->4 5 3 2 1 (바꾸고 난 후)
-> X값은 4. X값의 인덱스는 움직이지 않는다. Y값만 움직인다. 그럼 Y값은 3
-> X값 4와 Y값 3을 비교해본다.
->X값 4가 크니 Y값 3과 교체
이걸 끝까지 반복하면?
결과적으로 제일 작은 값(1)이 맨 앞에 온다.
이게 FOR문을 한번 돌은 것이다.
이것을 종이에 직접 그려서 해본다.
밑에는 예제 코드이다.
모든 코드를 복사 붙여넣기 하지 말고 직접 짜거나 종이에 적어본 후 하는 게
가장 직관적으로 알기 쉽고 오래 남는다.
for(x=0;x<n-1;x++) *N이 뭔지는 알았는데 왜 여기서 -1을 합니까?
{
for(y=x+1;y<n;y++)
}
N = 여기서 N이란 값은.
내가 선택정렬을 하고 싶은 배열 A[5] = 라는 배열이 있을 때,
N은 원소의 개수이다.
실제 배열에 들어있는 값
그러나 배열의 인덱스(A[0] 의 값은 1이다. 즉 0 1 2 3 4 인덱스값
그것은 바로 선택정렬의 X값은
마지막 까지 갈 필요가 없기 때문이다.
x y
1 2 3 5 4
->이렇게 마지막 값에 도착하면 두 값을 비교하고 X가 Y보다 크면 값을 바꿔준다.
->마지막 값은 자동적으로 제일 낮은 값이므로 비교해줄 값이 없다.
<예제 코드>
int temp = 0;
int x, y;
for(x = 0 ; x < 4 ; x++ )
{
for(y = x + 1 ; y<5 ; y++)
{
if(a[x] > a[y])
{
temp = a[x];
a[x] = a[y];
a[y] = temp;
}
}
}
댓글