스크래치COS-버블정렬

스크래치 COS -버블정렬

스크래치COS 코딩시험에서 알고리즘의 가장 핵심적인 부분이 변수, 반복문, 조건, 함수이다.

코딩에서 가장 기본이 되는 알고리즘 중 또다른 것은 정렬이다. 때로는 빠른 검색을 위해 정렬이라는 절차를 수행할 필요가 있다. 이번 글에서는 버블 정렬 알고리즈을 스크래치로 구현해볼 것이다.

그 중에서 버블정렬은 서로 이웃한 데이터들을 비교하여 가장 큰 데이터를 맨 뒤로 보내는 정렬 방식으로 데이터 수가 적을 때 효율적이다. 그러나 거의 정렬되어 있지 않을 때는 비효율적이다.

요구사항

리스트에 10개의 숫자를 1~100 사이의 난수를 발생하여 삽입한다.

입력한 리스트의 숫자값들 중에서 검색하기 위해 숫자를 입력하고 해당 숫자를 검색한다.

일 예로 아래와 같이 5개의 수가 있다고 해보자.

기본 개념을 이해하자, 가장 큰 수를 맨 뒤에 배치시키는 것이다.

앞에 수와 뒤에 수를 비교하여 큰수를 뒤로 보내는 것이다.

[스텝1]

* 첫번째로 큰 수를 정한다.

첫번째항목과 두번째 항목을 비교한다.

- 7과 12를 비교할 것이다.

큰 수가 12이기 때문에 현상태 유지이다.

[스텝2]

이번에는 2번째와 3번째 항목을 비교한다.

- 12와 4를 비교한다. (12가 크기 때문에 12는 3항목 자리로 이동하고, 3항목의 숫자 4는 2번째항목으로 이동한다.)

[스테3]

3번째항목과 4번째항목을 비교한다.

- 12와 21을 비교한다. 21이 크기 때문에 현상태를 유지한다.

[스텝4]

4번째항목과 5번째항목을 비교한다.

- 21과 2를 비교한다.(21이 크기 때문에 위치를 서로 맞바꾼다.

[스텝5]

* 두번째로 큰 수를 정한다.

다시 첫번째항목과 두번째 항목을 비교한다.

- 7과 4를 비교할 것이다. (큰 수가 7이기 때문에 위치를 맞바꾼다.)

[스텝2]

이번에는 2번째와 3번째 항목을 비교한다.

- 7와 12를 비교한다. (12가 크기 때문에 현상태를 유지한다.)

[스테3]

3번째항목과 4번째항목을 비교한다.

- 12와 1을 비교한다. 12가 크기 때문에 자리를 맞바꾼다.

다음은 세번째로 큰 수를 구하면 된다.

이런식으로 반복하여 하나씩 정렬해 나가는 것이 버블정렬이다.

분석 및 설계

. 변수만들기

- num : 10개의 숫자를 저장하는 리스트 변수이다.

- i : 리스트에 인덱스를 저장하는 변수이다.

- j : 리스트에 인덱스를 저장하는 변수이다.

- temp : 두 수를 교환하기 위해 수를임시저장하는 변수이다.

. 스프라이트

. 고양이 스프라이트 : 실제 입력과 검색을 행하는 스프라이트

. 입력 버튼 스프라이트 : 고양이 스프라이트에 '입력' 메시지를 보내는 스프라이트이다.

. 정렬 버튼 스프라이트 : 고양이 스프라이트에 '정렬' 메시지를 보내는 스프라이트이다.

. 초기화

. 입력 신호를 받았을 때

. num 리시트 변수의 항목을 모두 삭제하기

. 10회 반복하며 1~100 사이의 난수를 num 리스트에 추가한다.

. 버블정렬

. i에 num 리스트의 길이를 저정한다.

. i가 1일때까지 반복하기.

- j=1

. j=i까지 반복하기

- if num(j) > num(j+1), j, j+1 자리 맞교환

- j = j + 1

블럭코딩

. 입력 신호를 받았을 때
. num 리시트 변수의 항목을 모두 삭제하기
. 10회 반복하며 1~100 사이의 난수를 num 리스트에 추가한다.

정렬 신호를 받았을때
. i에 num 리스트의 길이를 저정한다.
. i가 1일때까지 반복하기.
- j=1
. j=i까지 반복하기
- if num(j) > num(j+1), j, j+1 자리 맞교환
- j = j + 1

* 디버깅

* 입력버튼을 클릭했을 때

* 정렬 버튼 스프라이트를 클릭했을 때

I=10(num의 길이)

[1스텝]

i=1까지 반복하기(i=10, false)

. j=1

. j=i까지반복하기( 1=10, false)
. num(1) > num(2) (97>4, true)
- num(1)=4, num(2)=97로 교환
. j=j+1 (2)

[2스텝]

i=1까지 반복하기(i=10. false)

. j=1

. j=i까지반복하기( 2=10, false)
. num(2) > num(3) (97>96, true)
- num(2)=96, num(3)=97
. j=j+1 (3)

[3스텝]

i=1까지 반복하기(i=10. false)

. j=1

. j=i까지반복하기( 3=10, false)
. num(3) > num(4) (97>5, true)
- num(3)=5, num(4)=97
. j=j+1 (4)

[4스텝]

i=1까지 반복하기(i=10. false)

. j=1

. j=i까지반복하기( 4=10, false)
. num(4) > num(5) (97>62, true)
- num(4)=62, num(5)=97
. j=j+1 (5)

[5스텝]

i=1까지 반복하기(i=10. false)

. j=1

. j=i까지반복하기( 5=10, false)
. num(5) > num(6) (97>90, true)
- num(4)=90, num(5)=97
. j=j+1 (4)

이런식으로 정렬을 해나간다.[중략]

j=9가 된 경우, 가장 큰 수가 정해진다. [97]

이제 i=9 (10에서 9로 1만큼 감소시켜서 1~9까지 비교하며 두번째로 큰 수를 찾는다.

위와 같이 1과 2, 2와 3, 3과 4, 4와 5, 6과 7, 7과 8, 8과 9를 비교하여 두번째로 큰 수는 다음과 같다.

이제 i=8 (10에서 9로 1만큼 감소시켜서 1~9까지 비교하며 세번째로 큰 수를 찾는다.

위와 같이 1과 2, 2와 3, 3과 4, 4와 5, 6과 7, 7과 8를 비교하여 세번째로 큰 수는 다음과 같다.

상기와 같은 식으로 반복하면 정렬이 된다.

* 실행 결과물

'입력' 버튼 스프라이트를 클릭했을 때 num 리스트 변수에 10개의 난수값이 추가된다.

정렬 버튼 스프라이트를 클릭하면 아래와 같이 num 리스트 변수가 정렬이 된다.

스크래치를 통해 버블정렬 알고리즘을 구현해보았다. 버블정렬은 반복문이 이중으로 반복하기 때문에 실행횟수가 많아서 많은 데이터를 정렬할 경우에는 속도가 느린 단점이 있다. 보통 빅 데이터의 경우에 백만건, 천만건 데이터를 버블정렬로 정렬하려면 많은 시간이 소요되어서 더 나은 알고리즘이 필요하다. 그래서 다양한 정렬 알고리즘이 개발되고 있고 활용되고 있다.

다시 한번 강조해서 말하지만, 변수의 값이 각 프로그램 단계별 순차적으로 어떻게 변화하는지 추척하는 것이 매우 중요하다. 블럭을 하나씩 쌓으면서 변수 볼륨 값의 변화를 살펴보자. 코딩은 눈으로 보면서 이해하고 학습하지만 직접 블럭을 쌓으며 이해하고 학습하는 것이 더 효과적이며 창의와 이해의 개념이 ~쑥 늘어납니다.

앞으로의 여러분의 모습을 기대합니다.

Just Do it!!!

Just Drag&Drop!!!

MagneticFieldSen

저작자표시 비영리 변경금지

'스크래치 > 스크래치 COS시험' 카테고리의 다른 글

스크래치COS-퀵정렬 (0)	2022.08.11
스크래치COS-선택정렬 (0)	2022.08.10
스크래치COS-선형검색 (1)	2022.08.08
스크래치COS-십진수를이진수로변환 (0)	2022.08.07
스크래치COS-이진수를십진수로변환 (0)	2022.08.06

enjoyCoding

스크래치COS-버블정렬

스크래치 COS -버블정렬