스크래치 COS -퀵정렬
스크래치COS 코딩시험에서 알고리즘의 가장 핵심적인 부분이 변수, 반복문, 조건, 함수이다.
코딩에서 가장 기본이 되는 알고리즘 중 또다른 것은 정렬이다. 때로는 빠른 검색을 위해 정렬이라는 절차를 수행할 필요가 있다. 이번 글에서는 퀵정렬 알고리즈을 스크래치로 구현해볼 것이다.
퀵정렬 알고리즘의 작동 방법은 divide and conquer로 이루어진다.
divide는 pivot을 선택하고, pivot보다 작으면 왼쪽으로, 큰 값은 오른쪽으로 나눕닏.
conquer는 왼쪽에 있는 리스트와 오른쪽에 있는 리스트를 정렬한다.
퀵정렬 예제로 리스트 {21 12 4 2 7} 가 있다.
마지막 갑을 piivot으로 잡는다.
여기서는 7를 pivot으로 잡고 작은 갑은 왼쪽으로 큰 값은 오른쪽으로 나눈다.
{4 2} 7 {21 12} 두 리스트로 나뉜다.
왼쪽 그룹 {4 2} 리스트에서 2를 pivot으로 잡고 진행한다.
정렬하면 {2 4} 가 되고
이제 오른쪽 리스트 {21 12} 리스트에서 pivot 12로 설정하고 정렬하면
{12 21}이 된다.
이제 더 이상 나눌 수 없으므로 combine을 진행하다.
{2 4} 7 {12 21}
-> 2 4 7 12 21 로 정렬이 된다.
요구사항
리스트에 5개의 숫자를 1~100 사이의 난수를 발생하여 삽입한다.
그리고 퀵 정렬 알고리즘을 활용하여 리스트를 정렬한다.
기본 개념은 선택한 수를 맨 왼쪽의 수와 맨 오른쪽의 수를 비교하여 작은 수는 왼쪽 수의 위치로 옮기고, 큰 수는 오른쪽의 수의 위치로 옮긴다.
변수 mid, pivot, i, j, temp
quicksort(left, right) {
#####
# pivot 값을 선택하고 맨뒤로 옮긴다.
#####
if left < right {
mid = (L + (R - 1))/2 -> 반올림
pivot = num(mid)
num(mid) = num(right)
num(right) = pivot
}
#######
# pivot값보다 크면 num(j)값을 num(i)값으로 옮긴다.(맞바꾼다.)
# i변수는 작은 값의 위치값이다.
# 만일 pivot보다 크면 j변수만 증가시킨다.
#
| 21 | 12 | 4 | 2 | 7 |
| i,j=1 | pivot |
#######
i=left
j=left
loop (j=right) { j는 1씩 증가시키면 반복한다.
if num(j) < pivot {
temp = num(i)
num(i) = num(j)
num(j) = temp
i = i + 1
} /* end of if */
j = j + 1
} /* end of loop */
기본 개념을 생각하세요(pivot보다 크면 그냥 j값만 증가시킨다.
이는 리스트에서 그냥 지나친다는 것이다.
반대로 pivot보다 작으면 i위치값(왼쪽, 작은값의 위치값)을 증가시켜 맞교환한다.
[스텝1]
if num(1) < pivot (21 < 7, false)
j = j + 1
| 21 | 12 | 4 | 2 | 7 |
| i, | j=2 | pivot |
[스텝2]
if num(2) < pivot (12 < 7, false)
j = j + 1
| 21 | 12 | 4 | 2 | 7 |
| i | j=3 | pivot |
[스텝3]
if num(3) < pivot (4 < 7, true)
num(1) <-> num(4) 맞교환
i = i + 1
j = j + 1
| 4 | 12 | 21 | 2 | 7 |
| i=2 | j=4 | pivot |
[스텝4]
if num(4) < pivot (2 < 7, true)
num(2) <-> num(4) 맞교환
i = i + 1
j = j + 1
| 4 | 2 | 21 | 12 | 7 |
| i=3 | j=5, pivot |
이제 반복문이 빠져나간다.
위의 테이블을 보시면, { 4 2 }와 { 21 12 } 값으로 나뉘어진다.
이제 할 일은 피봇값을 가운데 배치하는 것이다. 그 위치는 i 값이다
아래 문장을 실행할 것이다.
if num(i) > num(right)
temp = num(i)
num(i) = num(right)
num(right) = temp
}
quicksort(left, i-1)
quicksort(i+1, right)
}
if (num(i) > num(right) { 21 > 7 보다 크면 스위치하면 된다.
num(i) <-> num(right) 위치의 값을 맞바꾼다.
| 4 | 2 | 7 | 12 | 21 |
| i=3 | j=5, pivot |
위의 리스트를 보시면 pivot값 7을 기준으로
왼쪽에는 pivot값보다 작은 값 {4 2} 리스트가 있고,
오른쪽에는 pivot값보다 큰 값 {12 21} 리스트가 있다.
이제 왼쪽 리스트와 오른쪽 리스트를 다시 퀵소트를 호출하여 정렬한다.
quicksort(left, i-1)
quicksort(i+1, right)
분석 및 설계
. 변수만들기
- num : 10개의 숫자를 저장하는 리스트 변수이다.
- i : 리스트의 위치값을 저장하는 인덱스 변수이다.
- j : 리스트의 위치값을 저장하는 인덱스 변수이다.
- temp : 임시 저장 변수
- mid1 : 가운데 위치값을 저장하는 변수 (기준이 되는 위치 값)
- pivot : num(a), 가운데 위치의 숫자값을 저장한다.
* 퀵정렬 인자변수(left, right)
- left : 리스트의 왼쪽 위치를 저장하는 변수
- right : 리스트의 오른쪽 위치를 저장하는 변수
. 스프라이트
. 고양이 스프라이트 : 실제 입력과 검색을 행하는 스프라이트
. 입력 버튼 스프라이트 : 고양이 스프라이트에 '입력' 메시지를 보내는 스프라이트이다.
. 정렬 버튼 스프라이트 : 고양이 스프라이트에 '정렬' 메시지를 보내는 스프라이트이다.
. 초기화
. 입력 신호를 받았을 때
. num 리시트 변수의 항목을 모두 삭제하기
. 10회 반복하며 1~100 사이의 난수를 num 리스트에 추가한다.
. 퀵정렬
quicksort(left, right) {
#####
# pivot 값을 선택하고 맨뒤로 옮긴다.
#####
if left < right {
mid = (L + (R - 1))/2 -> 반올림
pivot = num(mid)
num(mid) = num(right)
num(right) = pivot
}
#######
# pivot값보다 크면 num(j)값을 num(i)값으로 옮긴다.(맞바꾼다.)
# i변수는 작은 값의 위치값이다.
# 만일 pivot보다 크면 j변수만 증가시킨다.
#
| 21 | 12 | 4 | 2 | 7 |
| i,j=1 | pivot |
#######
i=left
j=left
loop (j=right) { j는 1씩 증가시키면 반복한다.
if num(j) < pivot {
temp = num(i)
num(i) = num(j)
num(j) = temp
i = i + 1
} /* end of if */
j = j + 1
} /* end of loop */
블럭코딩
| . 입력 신호를 받았을 때 . num 리시트 변수의 항목을 모두 삭제하기 . 10회 반복하며 1~100 사이의 난수를 num 리스트에 추가한다. |
| 퀵정렬 신호를 받았을때 퀵정렬(1, num의 길이) num 말하기 |
| 퀵정렬(left, right) 함수 quicksort(left, right) { ##### # pivot 값을 선택하고 맨뒤로 옮긴다. ##### if left < right { mid = (L + (R - 1))/2 -> 반올림 pivot = num(mid) num(mid) = num(right) num(right) = pivot } ####### # pivot값보다 크면 num(j)값을 num(i)값으로 옮긴다.(맞바꾼다.) # i변수는 작은 값의 위치값이다. # 만일 pivot보다 크면 j변수만 증가시킨다. # ####### i=left j=left loop (j=right) { j는 1씩 증가시키면 반복한다. if num(j) < pivot { temp = num(i) num(i) = num(j) num(j) = temp i = i + 1 } /* end of if */ j = j + 1 } /* end of loop */ |
* 디버깅
디버깅은 위의 요구사항을 참고해서 분석해보기를 추천한다.
스스로 프로그램이 어떻게 동작하는 이해하는 것은 매우 중요하다.
* 실행 결과물
'입력' 버튼 스프라이트를 클릭했을 때 num 리스트 변수에 10개의 난수값이 추가된다.
퀵정렬 버튼 스프라이트를 클릭하면 아래와 같이 num 리스트 변수가 정렬이 된다.
스크래치를 통해 퀵정렬 알고리즘을 구현해보았다. 스크래치COS의 퀵정렬은 일반적인 상황 가운데에서는 가장 빠르다는 알고리즘이다. 물론 데이터의 정렬 상황에 따라 시간이 많이 소요되기도 하지만, 일반적으로는 가장 빠른정렬 시간을 갖는다.
이쯤되면 아~ 알고리즘이 너무 어려워, 하며 포기하는 사람들이 많을 것이다. 이번 프로그램의 동작 과정을 잘 이해하고 분석하기를 추천한다. 잘 모르시면 댓글을 남겨주세요.
다시 한번 강조해서 말하지만, 변수의 값이 각 프로그램 단계별 순차적으로 어떻게 변화하는지 추척하는 것이 매우 중요하다. 블럭을 하나씩 쌓으면서 변수 볼륨 값의 변화를 살펴보자. 코딩은 눈으로 보면서 이해하고 학습하지만 직접 블럭을 쌓으며 이해하고 학습하는 것이 더 효과적이며 창의와 이해의 개념이 ~쑥 늘어납니다.
앞으로의 여러분의 모습을 기대합니다.
Just Do it!!!
Just Drag&Drop!!!
'스크래치 > 스크래치 COS시험' 카테고리의 다른 글
| 스크래치COS-이진검색 (0) | 2022.08.12 |
|---|---|
| 스크래치COS-선택정렬 (0) | 2022.08.10 |
| 스크래치COS-버블정렬 (0) | 2022.08.09 |
| 스크래치COS-선형검색 (1) | 2022.08.08 |
| 스크래치COS-십진수를이진수로변환 (0) | 2022.08.07 |
댓글