|
정수값 10개를 읽어들여 이를 가장 작은 수에서 큰 수의 순으로 출력하는 프로그램을 작성하시오.
이는 전형적인 데이터 정렬의 문제이다. 데이터를 정렬할 때에는 일단 데이터들을 다 읽어들여야 하므로 반드시 배열이 필요하게 된다. 우선 정수값 10개를 읽어들여야 하므로 크기가 10인 정수 배열이 필요하다. 그 다음 읽어들인 10개의 정수값을 작은 수에서 큰 수의 순서로 정렬하는 것이 필요하다.
int ia[10];
● 정렬하는 방법에는 여러 가지가 있으나 여기서는 가장 간단한 방법을 사용하도록 하겠다. 우선 맨 처음 원소를 두 번째 원소와 비교한다. 그래서 두 번째 원소가 첫 번째 원소보다 작으면 두 원소의 위치를 바꾼다. 그 다음 역시 첫 번째 원소와 세 번째 원소를 비교하여 세 번째 원소가 첫 번째 원소보다 작으면 두 원소의 위치를 서로 바꾼다.
이와 같은 작업을 맨 끝의 원소까지 한다. 그러면 첫 번째 원소에는 데이터 중 가장 작은 것이 들어가게 된다. 왜냐하면 항상 첫 번째 원소와 비교하면서 더 작은 것을 첫 번째 원소에 오도록 했기 때문이다. 이제 첫 번째 원소에는 가장 작은 원소가 왔으므로 제자리를 찾은 것이다. 두 번째 원소를 역시 세 번째 원소부터 맨 끝의 원소까지 비교하면서 두 번째 원소보다 작으면 서로 자리를 바꾸게 된다. 그러면 역시 두 번째 원소에는 데이터 중 두 번째로 작은 값이 (가장 작은 값은 이미 첫 번째 원소에 들어있다) 들어가게 된다. 이와 같은 작업을 세 번째 원소부터 맨 마지막 원소 바로 전의 원소까지 하게 되면 바로 데이터가 정렬된다(맨 마지막 원소는 비교할 대상이 없으므로 할 필요가 없다).
1번 2번 3번 4번 5번 6번 7번 8번 9번 10번
10 9 8 7 6 5 4 3 2 1
| | | | | | | | | |
|---| | | | | | | | |
|--------| | | | | | | |
|-------------| | | | | | |
|------------------| | | | | |
|-----------------------| | | | |
|----------------------------| | | |
|---------------------------------| | |
|--------------------------------------| |
|-------------------------------------------|
1번과 2번을 비교하여 1번>2번 이면, 즉 2번이 1번보다 작으면.. 두 원소의 위치를 서로 바꾼다. 그럼 2번의 원소 9가 1번 자리로 오고 1번 자리의 원소인 10이 2번 자리로 가게 될 것이다. 이렇게 된다.
9 10 8 7 6 5 4 3 2 1
이제 다음 작업을 한다. 1번과 3번을 비교한다.
9 10 8 7 6 5 4 3 2 1
| |
|----------|
9 와 8 이다.
| |
|-----|
이제 여기서의 두 번째 원소인 8이 첫 번째 원소가 9보다 작다. 그러면 어떻게 해야 하는가? 물론 위치를 바꾼다.
이렇게 된다.
8 10 9 7 6 5 4 3 2 1
이제 다음 작업을 한다.
8 10 9 7 6 5 4 3 2 1
| |
|------------|
1번과 4번을 비교한다.
8 과 7 이다.
| |
|-----|
이제 여기서의 두 번째 원소인 7이 첫 번째 원소인 8보다 작다. 그러면 어떻게 해야 하는가? 당연히 또 바꿔야지..
이렇게 된다.
7 10 9 8 6 5 4 3 2 1
위의 작업을 계속하다보면 결국은 이렇게 될 것이다.
1 10 9 8 7 6 5 4 3 2 1
이제 첫 번째 원소와 모든 원소와의 비교는 끝났다. 그럼 여기서 끝? 말도 안되는 소리 !
이 단계에서부터 또 다시 태양은 떠오른다. 후훗..첫 번째 원소와 두 번째 원소의 비교를 다시 해보시라.. 뭐라구? 그건 지금 끝났는데 그걸 왜 또해? 그게 아니라 여기서부턴
1 10 9 8 7 6 5 4 3 2
|
|
|--> 요걸 첫 번째 원소라 생각하자 이거지..
지겹겠지만 여기까지만 해보자구..일단은 여기까지는 직접 알고리즘을 알고 있어야 다음엔 추측만으로 가능하거든..
자 시작하자구.. 아참.. 조오기 1번 자리에 있는 1 이라는 원소 말인데 얘는 이미 끝난 문제니까 빼버리고 나머지 숫자들만 가지고 해보자구 . 왜냐구? 신경쓰이잖어. 자자. 더 이상 묻는 사람은 빳데루를 줘야함다.
10 9 8 7 6 4 3 2
| |
|----|
자 첫 번째 원소 10 과 두 번째 원소 9 랑 비교를 해보자구.. 지겨워? 메롱...내가 아까 뭐라구 했어. 두 번째 원소가 작으면 첫 번째 원소랑 자리를 바꾸라고 했잖아. 이렇게 된다.
9 10 8 7 6 5 4 3 2
자. 이젠 대충 아는 내용일테니까 빨리빨리 가자구..
9 10 8 7 6 5 4 3 2
| |
|------|
9 8
| |
|------|
자 여기서의 첫 번째 원소인 9와 두 번째 원소인 8과 비교를 해봐. 두 번째 원소가 또 작으니까 첫 번째 원소와 자리를 바꿔야겠지? 넘 쉬운거 자꾸 하니까 열받았다구? 흠..
이렇게 된다.
8 10 9 7 6 5 4 3 2
더 빨리 가보자구.
7 10 9 8 6 5 4 3 2 이렇게 될꺼야..
6 10 9 8 7 5 4 3 2 이렇게 될꺼야..하앗. 초 스피드
5 10 9 8 7 6 4 3 2 우하핫...눈돌아가지?
4 10 9 8 7 6 5 3 2 크하핫..정신없지?
3 10 9 8 7 6 5 4 2 음음..심각하군..
* 2 10 9 8 7 6 5 4 3 에구 끝났네..
|
|
|
|->아까 요기 헷갈릴까봐 빼버렸던 1이 있었더랬지..
종합해 보자구..
1 2 10 9 8 7 6 5 4 3
어때? 계속 이런 식으로 하다보면 순서대로 정렬이 될 거 같다는 생각이 안들어? 음..난 드는데..
위와 같은 정렬 방법을 버블 정렬(bubble sort) 방법이라고 한다.
자 아까 정수배열 ia[10] 을 주었지..
|
|
|--> 요건 말야 배열인데..ia라는 기본변수에 10개의 방을 배정하라는 소리지
ia 라는 integer arrangment라는 의미로 지은 변수명이야. 별거아니지 신경쓸 거는 업구. 사실 변수명은 아무렇게나 짓는 거니까.. 어쨌든 ia[10] 라구 선언을 하였으니 다음과 같은 배열이 생길거야..
ia[00] ia[01] ia[02] ia[03] ia[04] ia[05] ia[06] ia[07] ia[08] ia[09]
말하자면 변수 10개를 수고하며 코딩할 필요가 없이 ia[10] 이라는 배열선언문 하나만으로 만들 수 있는거지..합리적이지?
그러니까 자넨 이 배열선언문으로 위 네모 칸에 들어있는 10개의 변수가 만들어 졌다구 생각하란 말야. 알겠지?
● 이제 기술적으로 어려운 부분은 두 원소를 서로 자리 바꾸도록 하는 것이다. 자리를 바꾼다는 것은 두 변수의 값을 서로 교환하는 것을 의미하는데 예를 들어 변수 i 와 변수 j 가 서로 값을 교환하게 되면 변수는 i 는 변수 j 의 값을 갖게 되며, 변수 j 는 변수 i의 값을 갖게 된다. 그런데
ia[00] ia[01] ia[02] ia[03] ia[04]
10 9 8 7 6
| |
|--------|
|
|---> 교환한다고 생각해보자.
프로그램상으론 변수 ia[00]에 들어있는 10 이라는 값을 ia[01]에 들어있는 9라는 값과 교환하여야 한다는 소리다.
그런데 말이다. 그런데... 다음과 같이 프로그램을 작성하면 안된다.
i = j;
j = i;
위와 같이 하면 안되는 이유는 'i = j;'라고 하면 변수 i가 j의 값을 이미 가져 이전의 i의 값이 사라지기 때문이다. 말하자면
10 9 8 7 6
| |
| |--> 요걸 j 라는 변수에 넣었다고 치자.
|
|--> 요걸 i 라는 변수에 넣었다고 치고
이를 정렬해보자.
10과 9를 바꾼다. i = 10 , j = 9 이므로
i = j;
j = i;
위와 같이 하면 i 는 j 의 값을 가지게 되어 기존에 가지고 있던 값인 10을 잃어버리게 된다. 오케이?
그럼 이제 i 는 9의 값을 갖게 되었다.
j = i;
이 문장을 실행시키면 j는 도로 i가 된다. i도 9가 되고 j도 9가 된다. 결국 같은 값을 갖게 된다. 어쩐지 이래서는 안된다는 기분이 들지 않는가? 그럼 오케이..더 이상 파고 들어갈 필요는 없다. 머리만 아프니까. 그러면 어떻게 해야 되는가? 이 경우에는 임시 변수를 하나 사용하면 된다. 즉 임시 변수에 i의 값을 기억시켜 놓은 다음 이를 활용하면 되는데, 다음과 같이 하면 된다.
t = i;
i = j;
j = t;
위에서는 't'라는 임시 변수를 사용하여 i의 값을 일시 보관하고 있다. 따라서 i = j 라는 문장으로 i의 값을 잃어버려도 t에 이 값이 기억되어 있으므로 j 에는 i의 값이 들어가게 된다. j = t 라는 문장으로 말이다.
따라서 i와 j의 값이 서로 뒤바뀌게 된다.
10 9 8 7 6
| |
| |--> 요걸 j 라는 변수에 넣었다고 치자.
|
|--> 요걸 i 라는 변수에 넣었다고 치고
★ t 라는 임시변수를 만든다. t 에다가 i의 값 10을 넣는다. t는 i의 값을 이제 기억하였다.
i = j 라는 문장으로 10과 9를 버블정렬 개봉박두..
i 에는 9가 기억되었다. 말하자면 첫 번째 원소의 자리에 9가 왔다.
하지만 아직은 첫 번째 자리의 원소인 10이 두 번째 자리로 간 것은 아니다.
만약 여기서 무식하게 j = i 라고 해버리면
9 9 8 7 6
| |
|---|
|
|--> 요렇게 되버리는 불상사가 발생하게 된다.
그래서 t 에다가 i 의 값인 10을 기억시키는 작업이 필요한 것이다.
자 t 에 i 의 값이 기억되었다.
t = i 즉 t = 10
i = j 9 9 8 7 6
j = t 9 10 8 7 6
이렇게 되지롱.. | 
댓글을 달아 주세요