| sitelink1 | |
|---|---|
| sitelink2 | |
| extra_vars5 | |
| extra_vars6 |
http://myhome.hanafos.com/~log0/visual_basic.htm
비베 한달이면 한국불패만큼 한다. - 9 . 소트 -
프로그래머라면 누구나 소팅(SORTING)을 할 줄 알아야 합니다.
소팅이란 어떤 자료테이블을 크기 순으로 재배열 하는 것을 말하는데요. 만약
3,4,2,1,6,7,9,8,10,5
이란 자료테이블이 있다고 할때요. 이것을 소팅하면
1,2,3,4,5,6,7,8,9,10과 10,9,8,7,6,5,4,3,2,1이 되는 것입니다.
앞에것은 오름차순에 의한 소트(SORT BY ASCENDING ORDER)라 하고요.
뒤의 것은 내림차순에 의한 소트(SORT BY DESCENDING ORDER)라고 합니다.
1. SELECTION SORT
선택소트법을 가르쳐 드리겠습니다.
제가 국민학교 다니던 시절 경시반선생님이 가르쳐주신 방법인데 여러가지 소팅법중 가장쉽고 효율은 좀떨어지는 그런
방법입니다.
선택 소트법을 하기전에 간단하게 최소값과 최대값을 구하는 것을 해보겠습니다.
만약 위에 있는 숫자 테이블에서 가장 큰 수를 또는 가장 작은 수를 뽑아 내라고 한다면 어떤 방법으로 하시겠습니까?
한번 생각해보시고 프로그래밍을 해보셔도 좋겠네요. 아마 다들 아실것이라 생각 됩니다.
예전 국민학생들이 베이직을 8비트로 배울때 3개월정도 하면 이것을 가르쳐 주었거던요.
그만큼 쉽습니다. 저도 MSX로다 이걸 배웠습니다.
(소스는 테이블이 있다고 가정합니다.)
FOR I = 1 TO 9
IF TABLE(I) > TABLE(I+1) THEN TABLE(I+1) = TABLE(I)
NEXT I
이렇게 하면 마지막에 살아남는 TABLE(10)값이 최대값이 됩니다.
실제 해보시면 압니다.
그럼 선택 소트 기법과 최대값 구하는 것과 무슨 상관이냐 하시겠지만 상관이 있습니다.
위 소스에서는 최대값이 앞으로 나아가면서 전부 최대값 으로 만들어 버리고 지나갑니다.
그래서 원래의 자료를 다치지 않고 지나가게 만들어 보면 이렇게 됩니다.
FOR I=1 TO 9
IF TABLE(I)>TABLE(I+1) THEN
TEMP=TABLE(I+1)
TABLE(I+1)=TABLE(I)
TABLE(I)=TEMP
END IF
NEXT I
이렇게 하면 최대값이 마지막으로 가면서 자리만을 바꾸고 지나갑니다.
그래서 자료는 다치지 않습니다. 이런식으로 전구간에서 최대값을 구합니다.
그리고는 마지막으로 최대값을 보냅니다.
그다음에는마지막 숫자를 제외하고 9개의 숫자중에서 최대값을 구합니다.
그래서 9번째에 보냅니다. 다시 8개의 숫자중 최대값을 구해서 8번째에 붙입니다.
다시 7개의 숫자중에서 최대값을 구합니다. 그래서는 7번째에 붙입니다.
이런식으로 10번만 해주면 내림차순으로 소트가 되는 것이죠.
이런 방식을 선택소트 라고 합니다. 아래는 완성된 소스입니다.
FOR H=9 TO 1 STEP -1
FOR I=1 TO H
IF TABLE(I)>TABLE(I+1) THEN
TEMP=TABLE(I+1)
TABLE(I+1)=TABLE(I)
TABLE(I)=TEMP
END IF
NEXT I
NEXT H
쉽죠.^^ 그렇지만 성능이 떨어집니다.
물론 이런 숫자10개 소트하는 거야 문제없지만 만약 60,000개의 숫자를 선택소트법에 의해서 소팅을 한다면 비교회수는
((60000)^2)/2 = 약 1.8 * 10^9 번을 소팅해야 합니다.
정말 어마어마한 계산회수입니다.
만약 1초에 1,000,000번의 비교가 가능한 컴퓨터가 계산을 한다면 약 30분이 소모됩니다.
음 좀옛날 자료라 요즘 컴퓨터는 어떨지 모르겠군요...
2. 인덱스 값을 붙이는 방법
단지 소트를 하는 것만으로도 위의 알고리즘은 가치가 있지만
위의 알고리즘을 이용해 인덱스 번호를 붙이는 방법을 가르쳐 드리겠습니다.
인덱스 값이라고 하는 것은 자료 자체를 의미하는 것이 아니라 자료의 색인값을 말하는데요.
예를 들면 학번 같은경우 이름의 인덱스 값이라고 할수 있습니다.
34는 제 인덱스번호인 샘입니다.
아무튼 소트를 해서는 크기순으로 인덱스 번호를 붙이는 방법은 이렇습니다.(N은 자료의 갯수를 의미합니다.)
FOR I=1 TO N
FOR J=1 TO I
IF TABLE(I) <= TABLE(J) THEN INDEX(I) = INDEX(I) + 1
IF TABLE(I) > TABLE(J) THEN INDEX(J) = INDEX(J) + 1
NEXT J
NEXT I
인덱스번호를 저장할 INDEX()라는 배열을 하나 정의하고요.
1번 자료의 인덱스 값을 INDEX(1)에 자료2번의 인덱스 번호는 INDEX(2)에 넣는 식으로 했습니다.
자료는 숫자로 된 아무자료나 좋습니다. 만약 TABLE()가 이렇다면
25,57,48,37,12,92,86,23
인덱스 번호는 3,6,5,4,1,8,7,2가 되는 것이죠.
92의 인덱스 번호는 8이며 12의 인덱스 번호는 1입니다.
이것은 92가 가장큰 숫자이며 12가 가장 작은숫자임을 의미하는 것입니다.
설명할 것도 없겠지만 위의 소스를 설명 하자면요.
TABLE(1)과 TABLE(1)~TABLE(10)과 비교를 합니다.
그래서는 자신보다 작은 것이 나오거나 같은 것이 나올때 +1을 해주는 것입니다.
위의 소스에서 FOR J=1 TO I 라고 한것은 매번 중복되는 것이 있기때문이죠.
그러니까 TABLE(1)은 TABLE(1)하고만 비교하면 TABLE(2)가 TABLE(1)과 비교할때 TABLE(2)와 비교가 되고
TABLE(3)이 TABLE(1)과 비교할때 또 비교가 되므로 TABLE(1)은 TABLE(1)하고만 비교해보면 되고요.
TABLE(2)는 TABLE(1)과 TABLE(2)와 TABLE(3)은 TABLE(1)과 TABLE(2), TABLE(3)과 비교를 하면 되는 것이죠.
음.. 오히려 설명이 더욱 이해를 어렵게 한것 같네요.
그냥 소스를 열심히 보시면 이해가 될것입니다.
3. 문자를 소트 하는 방법
문자는 숫자와 달라 대소를 비교할 수 없다고 생각하기 쉽습니다.
하지만 문자역시 대소 비교가 가능합니다.
저역시 이것을 모르고 ASC함수를 이용해 문자를 소팅하는 어리석은 생활을 했습니다. --;;
문자역시 대소 비교가 가능합니다.(참고 : ASC함수는 문자의 아스키코드값을 반환합니다.)
IF "A" < "B" THEN BEEP
하시면 삐~~~ 할겁니다.^^
4. 다른 소트기법
감소 간격 소트(DIMINISHING INCREMENT SORT)라는 소트 기법이 있습니다.
흔히들 SHELL소트라고 하는 것인데요.
1959년 Donald L. Shell에 의해 제안된 방법인데요.
그이후로 Shell소트로 불리고 있습니다.
이 소트에 대해 자세히 알고 싶은 분은 메일을 주십시오. 오늘은 여기까지만 하죠.^^
--------------------------------------------------------------------------------
|
비베강좌(9)<--소트 |
비베 한달이면 한국불패만큼 한다. - 9 . 소트 -
프로그래머라면 누구나 소팅(SORTING)을 할 줄 알아야 합니다.
소팅이란 어떤 자료테이블을 크기 순으로 재배열 하는 것을 말하는데요. 만약
3,4,2,1,6,7,9,8,10,5
이란 자료테이블이 있다고 할때요. 이것을 소팅하면
1,2,3,4,5,6,7,8,9,10과 10,9,8,7,6,5,4,3,2,1이 되는 것입니다.
앞에것은 오름차순에 의한 소트(SORT BY ASCENDING ORDER)라 하고요.
뒤의 것은 내림차순에 의한 소트(SORT BY DESCENDING ORDER)라고 합니다.
1. SELECTION SORT
선택소트법을 가르쳐 드리겠습니다.
제가 국민학교 다니던 시절 경시반선생님이 가르쳐주신 방법인데 여러가지 소팅법중 가장쉽고 효율은 좀떨어지는 그런
방법입니다.
선택 소트법을 하기전에 간단하게 최소값과 최대값을 구하는 것을 해보겠습니다.
만약 위에 있는 숫자 테이블에서 가장 큰 수를 또는 가장 작은 수를 뽑아 내라고 한다면 어떤 방법으로 하시겠습니까?
한번 생각해보시고 프로그래밍을 해보셔도 좋겠네요. 아마 다들 아실것이라 생각 됩니다.
예전 국민학생들이 베이직을 8비트로 배울때 3개월정도 하면 이것을 가르쳐 주었거던요.
그만큼 쉽습니다. 저도 MSX로다 이걸 배웠습니다.
(소스는 테이블이 있다고 가정합니다.)
FOR I = 1 TO 9
IF TABLE(I) > TABLE(I+1) THEN TABLE(I+1) = TABLE(I)
NEXT I
이렇게 하면 마지막에 살아남는 TABLE(10)값이 최대값이 됩니다.
실제 해보시면 압니다.
그럼 선택 소트 기법과 최대값 구하는 것과 무슨 상관이냐 하시겠지만 상관이 있습니다.
위 소스에서는 최대값이 앞으로 나아가면서 전부 최대값 으로 만들어 버리고 지나갑니다.
그래서 원래의 자료를 다치지 않고 지나가게 만들어 보면 이렇게 됩니다.
FOR I=1 TO 9
IF TABLE(I)>TABLE(I+1) THEN
TEMP=TABLE(I+1)
TABLE(I+1)=TABLE(I)
TABLE(I)=TEMP
END IF
NEXT I
이렇게 하면 최대값이 마지막으로 가면서 자리만을 바꾸고 지나갑니다.
그래서 자료는 다치지 않습니다. 이런식으로 전구간에서 최대값을 구합니다.
그리고는 마지막으로 최대값을 보냅니다.
그다음에는마지막 숫자를 제외하고 9개의 숫자중에서 최대값을 구합니다.
그래서 9번째에 보냅니다. 다시 8개의 숫자중 최대값을 구해서 8번째에 붙입니다.
다시 7개의 숫자중에서 최대값을 구합니다. 그래서는 7번째에 붙입니다.
이런식으로 10번만 해주면 내림차순으로 소트가 되는 것이죠.
이런 방식을 선택소트 라고 합니다. 아래는 완성된 소스입니다.
FOR H=9 TO 1 STEP -1
FOR I=1 TO H
IF TABLE(I)>TABLE(I+1) THEN
TEMP=TABLE(I+1)
TABLE(I+1)=TABLE(I)
TABLE(I)=TEMP
END IF
NEXT I
NEXT H
쉽죠.^^ 그렇지만 성능이 떨어집니다.
물론 이런 숫자10개 소트하는 거야 문제없지만 만약 60,000개의 숫자를 선택소트법에 의해서 소팅을 한다면 비교회수는
((60000)^2)/2 = 약 1.8 * 10^9 번을 소팅해야 합니다.
정말 어마어마한 계산회수입니다.
만약 1초에 1,000,000번의 비교가 가능한 컴퓨터가 계산을 한다면 약 30분이 소모됩니다.
음 좀옛날 자료라 요즘 컴퓨터는 어떨지 모르겠군요...
2. 인덱스 값을 붙이는 방법
단지 소트를 하는 것만으로도 위의 알고리즘은 가치가 있지만
위의 알고리즘을 이용해 인덱스 번호를 붙이는 방법을 가르쳐 드리겠습니다.
인덱스 값이라고 하는 것은 자료 자체를 의미하는 것이 아니라 자료의 색인값을 말하는데요.
예를 들면 학번 같은경우 이름의 인덱스 값이라고 할수 있습니다.
34는 제 인덱스번호인 샘입니다.
아무튼 소트를 해서는 크기순으로 인덱스 번호를 붙이는 방법은 이렇습니다.(N은 자료의 갯수를 의미합니다.)
FOR I=1 TO N
FOR J=1 TO I
IF TABLE(I) <= TABLE(J) THEN INDEX(I) = INDEX(I) + 1
IF TABLE(I) > TABLE(J) THEN INDEX(J) = INDEX(J) + 1
NEXT J
NEXT I
인덱스번호를 저장할 INDEX()라는 배열을 하나 정의하고요.
1번 자료의 인덱스 값을 INDEX(1)에 자료2번의 인덱스 번호는 INDEX(2)에 넣는 식으로 했습니다.
자료는 숫자로 된 아무자료나 좋습니다. 만약 TABLE()가 이렇다면
25,57,48,37,12,92,86,23
인덱스 번호는 3,6,5,4,1,8,7,2가 되는 것이죠.
92의 인덱스 번호는 8이며 12의 인덱스 번호는 1입니다.
이것은 92가 가장큰 숫자이며 12가 가장 작은숫자임을 의미하는 것입니다.
설명할 것도 없겠지만 위의 소스를 설명 하자면요.
TABLE(1)과 TABLE(1)~TABLE(10)과 비교를 합니다.
그래서는 자신보다 작은 것이 나오거나 같은 것이 나올때 +1을 해주는 것입니다.
위의 소스에서 FOR J=1 TO I 라고 한것은 매번 중복되는 것이 있기때문이죠.
그러니까 TABLE(1)은 TABLE(1)하고만 비교하면 TABLE(2)가 TABLE(1)과 비교할때 TABLE(2)와 비교가 되고
TABLE(3)이 TABLE(1)과 비교할때 또 비교가 되므로 TABLE(1)은 TABLE(1)하고만 비교해보면 되고요.
TABLE(2)는 TABLE(1)과 TABLE(2)와 TABLE(3)은 TABLE(1)과 TABLE(2), TABLE(3)과 비교를 하면 되는 것이죠.
음.. 오히려 설명이 더욱 이해를 어렵게 한것 같네요.
그냥 소스를 열심히 보시면 이해가 될것입니다.
3. 문자를 소트 하는 방법
문자는 숫자와 달라 대소를 비교할 수 없다고 생각하기 쉽습니다.
하지만 문자역시 대소 비교가 가능합니다.
저역시 이것을 모르고 ASC함수를 이용해 문자를 소팅하는 어리석은 생활을 했습니다. --;;
문자역시 대소 비교가 가능합니다.(참고 : ASC함수는 문자의 아스키코드값을 반환합니다.)
IF "A" < "B" THEN BEEP
하시면 삐~~~ 할겁니다.^^
4. 다른 소트기법
감소 간격 소트(DIMINISHING INCREMENT SORT)라는 소트 기법이 있습니다.
흔히들 SHELL소트라고 하는 것인데요.
1959년 Donald L. Shell에 의해 제안된 방법인데요.
그이후로 Shell소트로 불리고 있습니다.
이 소트에 대해 자세히 알고 싶은 분은 메일을 주십시오. 오늘은 여기까지만 하죠.^^
--------------------------------------------------------------------------------
