로또 번호를 순서대로 - 코딩수업#9
데이터 정렬하기
이제 간단한 예제를 이용하여 코딩이 무엇인지 맛을 보았고 3가지 코딩의 기본 기능에 대하여 배웠다.
이러한 기본 지식을 이용하여 컴퓨터 프로그램을 배울 때 가장 먼저 배우게 되는 정렬과 검색에 대하여 이야기해 보겠다.
내가 가장 사랑하는 예제인 로또로 다시 돌아가 보자 ^^
6개의 공을 뽑는 방법은 앞선 코딩수업 #5에서 배웠다.
만일 그 공이 "40,7,25,3,17,39"라고 해보자.
이 번호를 들고 로또 추첨 결과를 본다면, 숫자를 하나씩 맞추기 위해 6개의 숫자 모두를 살펴보아야 할 것이다. 물론 6개의 숫자를 서로 비교한다는 것은 그리 어려운 일이 아니다.
그러나 500개의 숫자를 가지고 이러한 일을 한다면 그건 그리 쉬운 일이 아닐 것이다.
정렬하기
그래서 컴퓨터 자료구조론의 가장 중요 영역에 데이터의 정렬 부분이 놓이게 된다.
일단 편의상 6개의 숫자를 순서대로 놓는 작업을 해보자.
6개의 숫자는 눈으로 보아도 금방 그 순서를 정할 수 있다.
그러나 100개 또는 10,000개의 숫자를 순서대로 놓을 때도 사용할 수 있는 방법을 마련해야 한다.
그것을 일반화라고 했던가?
데이터를 순서대로 놓는 방법으로는 수많은 방법이 있고, 그중 머리로 가장 이해하기 쉬운 방법을 하나 소개한다. 그 방법은 아래의 그림으로 간단히 도식화해본다.
위의 도식을 5개의 그룹으로 나누어 보자.
1. 첫 번째 공에 가장 낮은 숫자를 가지고 오려면 두 번째부터 6번째까지 공과 첫 번째 공을 계속 비교하면서 첫 번째 공보다 더 낮은 숫자의 공이 있을 경우 그 공을 첫 번째와 교환하여 첫 번째 자리에 두면 된다.
- 1단계에서 40과 7의 순서를 바꾸어 첫 번째 공에 7이 자리하게 된다.
- 2단계에서는 7과 25의 순서가 바로 놓여 있으므로 변화가 없고,
- 3단계에서는 7과 3을 교환하여 3이 첫 번째 자리에 오게 된다.
- 4~5단계까지는 3보다 작은 숫자가 없으므로 3은 첫 번째 자리를 차지하게 된다.
2. 두 번째 공에 그다음 낮은 숫자를 가져오는 과정도 첫 번째 공의 그것과 다를 것이 없다.
위의 그림처럼 40과 25, 25와 7이 그 순서를 바로 잡게 된다.
3,4,5에서도 세 번째 공, 네 번째 공 , 다섯 번째 공에 낮은 숫자를 순서대로 가져오면 된다.
여섯 번째 공은 당연히 최고로 큰 숫자이므로 5번째 공까지만 이러한 과정을 반복하면 된다.
이 과정을 코딩으로 풀려면 1. 변수와 대입 , 2. 반복, 3. 조건 비교 세 가지 모든 방법을 동원해야 한다.
그 과정을 살펴보자.
코딩수업#5에서 정의한 변수에 위의 숫자가 뽑혔다고 가정하면
var result=[ 40 , 7 , 25 , 3 , 17 , 39 ]; // 6개의 숫자가 들어갈 방(변수)을 만든다.
var tmp; // 비교한 공을 교환하기 위한 변수를 미리 마련한다.
for (var i=0; i<5;i++){ // 1~5번째 공에 반복하여 처리한다.
for (var j=i+1;j<6;j++){ // 현재 비교할 대상의 공 이후의 공과의 비교를 반복한다.
if (result[i]>result[j]){ // 만일 비교한 공의 위치가 맞지 않다면
tmp=result[i]; // 두 숫자를 서로 교환하기 위하여 변수 tmp에 첫 숫자를 대입하고
result[i]=result[j]; // 작은 숫자를 그 자리에 옮기고(대입)
result[j]=tmp; // 변수 tmp의 숫자를 큰 숫자의 자리에 옮긴다.
}
}
}
document.writeln(result);
개발도구에서 실행해 보면 위와 같이 정렬된 숫자를 출력할 수 있다.
아무리 간단한 프로그램도 코딩의 세 가지 요소 대입, 반복, 비교를 수행해야 완성시킬 수 있다는 것을 보여준다.
위의 예제를 10,000개의 숫자를 정렬하기 위한 프로그램으로 바꾸려면,
for (var i=0; i<9999;i++){ // 1~9999번째 공에 반복하여 처리한다.
for (var j=i+1;j<10000;j++){ // 선택한 숫자 다음 숫자부터 비교
이와 같이 비교의 범위만을 바꾸어 반복처리해 주면 된다.
그리 효율적이지 않은 방법일 수도 있지만, 가장 이해하기 쉬운 방법의 정렬을 보여 준 것이다.
