스크래치COS-선택정렬

스크래치 COS -선택정렬

 

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

 

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

 

선택 정렬은 데이터들 중에서 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해 나가는 방식이다. 선택이란 용어를 사용한 것은 가장 작은 데이터를 선택하여 위치를 정한다는 개념으로 사용한 것 같다.

 

요구사항

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

그리고 선택 정렬 알고리즘을 활용하여 리스트를 정렬한다.

 

아래는 선택정렬 알고리즘의 예시이다.

 

먼저 숫자들 중에서 가장 작은 값을 찾는다. 가장 작은 값은 첫번째 항목에 위치를 시킬 것이다.

 

7

12

4

21

2

[스텝1]

* 리스트에서 가장 작은 값을 찾는다.

가장 작은 값은 다섯번째에 위치한 2값이다.

첫번째항값 7과 다섯번째항 2 값의 위치를 맞교환한다.

num(1)=2, num(5)=7이 된다.

 

2

12

4

21

7

 

[스텝2]

이번에는 2번째로 작은 값을 찾는다.

  - 찾을 때, 1부터가 아니라, 2번째 항목부터 검색해서 가장 작은 값을 찾는다.

  - 검색하니까 세번째항목값 4가 가장작다.

  - num(2)=4, num(3)=12로 교환한다.

 

2

4

12

21

7

 

[스텝3]

이번에는 3번째로 작은 값을 찾는다.

  - 찾을 때, 1, 2부터가 아니라, 3번째 항목부터 검색해서 가장 작은 값을 찾는다.

  - 검색하니까 다번째항목값 7가 가장작다.

  - num(3)=7, num(5)=12로 교환한다.

 

2

4

7

21

12

 

[스텝4]

이번에는 4번째로 작은 값을 찾는다.

  - 찾을 때, 1, 2, 3부터가 아니라, 4번째 항목부터 검색해서 가장 작은 값을 찾는다.

  - 검색하니까 다번째항목값 12 가장작다.

  - num(4)=12, num(5)=21로 교환한다.

 

2

4

7

12

21

 

이렇게 해서 선택정렬은 종료가 된다.

 

분석 및 설계

. 변수만들기

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

  - i : 첫번째 반복문의 리스트의 크기를 한 번에 하나씩 줄여나가는 역할을 한다.

  - j : 이미 정렬되고 남은 부분 리스트에서 가장 작은 값을 찾기 위해 사용된다.

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

  - min : 가장 작은 값을 임시로 저장하는 변수이다.

 

. 스프라이트

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

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

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

 

스크래치COS-선택정렬 스프라이트

 

. 초기화

 

. 입력 신호를 받았을 때

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

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

 

. 선태정렬

  . i = 1

  . i=10까지 반복하기

    - min = i

    - j = i + 1

      . j=11 까지 반복하기

        - if num(j) < num(min), min = j

        - j = j + 1

    - num(i), num(min) 값 맞교환

    - i = i + 1

 

블럭코딩

 

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

 

스크래치COS-선택정렬 입력신호를 받았을때

 

정렬 신호를 받았을때   . i = 1   . i=10까지 반복하기     - min = i     - j = i + 1       . j=11 까지 반복하기         - if num(j) < num(min), min = j         - j = j + 1     - num(i), num(min) 값 맞교환     - i = i + 1

 

스크래치COS-선택정렬 알고리즘

 

* 디버깅

* 입력버튼을 클릭했을 때

 

스크래치COS-선택정렬 입력데이터

 

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

 

스크래치COS-선택정렬 결과

 

 

i=5(num의 길이)

 

40

29

14

16

91

 

 

* 첫번째 가장 작은 값을 찾는다.

[1스텝]

i=1

i=5까지 반복하기

  . min=i  (1)

  . j = i+1 (1+1, 2)

. j=6까지 반복하기 (2=6, false)     . if num(j) < num(min) (num(2) < num(1)  (29 < 40, true)        min=j  (min=2)     . j = j + 1(3)

 

[스텝2]

i=5까지 반복하기

  . min=i  (1)

  . j = i+1 (1+1, 2)

. j=6까지 반복하기 (3=6, false)     . if num(j) < num(min), nuum(3) < um(2) (14 < 29, true)       . min=j  (min=3)     . j = j + 1(4)

 

[스텝3]

i=5까지 반복하기

  . min=i  (1)

  . j = i+1 (1+1, 2)

. j=6까지 반복하기 (4=6, false)     . if num(j) < num(min), num(4) < num(3)  (16 < 14, false)     . j = j + 1(5)

 

[스텝5]

i=5까지 반복하기

  . min=i  (1)

  . j = i+1 (1+1, 2)

. j=6까지 반복하기 (5=6, false)     . if num(j) < num(min), num5) < num(3) (91< 14, false)     . j = j + 1(6)

 

[스텝6]

i=5까지 반복하기

  . min=i  (1)

  . j = i+1 (1+1, 2)

. j=6까지 반복하기 (6=6, false)   . 스왑 : num(i)<->num(min) => num(1) <-> num(3)

i=i+1(2)

14

29

40

16

91

 

 

* 두번째로 작은 수 찾기

[스텝7]

 

i=5까지 반복하기

  . min=i  (2)

  . j = i+1 (2+1, 3)

. j=6까지 반복하기 (3=6, false)     . if num(3) < num(2)  (40< 29, false)     . j = j + 1(4)

 

[스텝8]

* 두번째로 작은 수 찾기

i=5까지 반복하기

  . min=i  (2)

  . j = i+1 (2+1, 3)

. j=6까지 반복하기 (4=6, false)     . if num(4) < num(2)  (29 < 40, true)        min=j  (min=4)     . j = j + 1(4)

 

 

중략...

 

이런식으로 반복해서 선택정렬 단계들이 진행된다.

단계를 밟아가면서 가장 중요한 것은 min변수 값과 i변수값 그리고 j 변수값의 변화를 유심히 꼼꼼하게 살펴보고 분석해보자. 그러면 선택 정렬 알고리즘을 이해하게 될 것이다.

 

 

 

* 실행 결과물

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

 

스크래치COS-선택정렬 입력데이터

 

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

 

스크래치COS-선택정렬 실행결과 화면

 

스크래치를 통해 선택정렬 알고리즘을 구현해보았다. 스크래치COS의 선택정렬은 가장 기본적인 알고리즘으로 각 변수의 변화되는 값들을 이해하고 분석할 필요가 있다. 선택정렬 알고리즘의 기본적인 개념은 리스트의 값들 중에서 가장 작은 값을 찾아서 일렬로 하나씩 채워나간다는 개념이다. 이를 프로그램으로 구현한 것이 이번 선택정렬 알고리즘이다.

 

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

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

 

Just Do it!!!

Just Drag&Drop!!!

 

MagneticFieldSen