10. 정렬 알고리즘을 활용해서 카드 정리하기
1정렬 알고리즘으로 카드 정리하기
도서관의 책들이 정리가 돼 있지 않으면 어떤 불편한 점이 있을까? 보고 싶은 책을 쉽게 찾기가 힘들 것이다. 하지만 학교 도서관이나 지역의 도서관에 가면 책들이 정리되어 있다. 그래서 우리는 우리가 보고 싶은 책들을 쉽게 찾아서 빌릴 수도 있고, 그 자리에서 볼 수도 있다.
컴퓨터도 마찬가지다. 컴퓨터의 많은 자료가 정리되어 있지 않다면 어떤 일이 생길까? 우리가 도서관에서 책을 빌릴 때 정리가 되지 않으면 책을 찾는데 시간이 오래 걸리듯이, 컴퓨터에서 정보를 찾는데 많은 시간이 걸릴 것이다. 그래서 컴퓨터는 항상 정보들을 정리하는 방법이 정렬 알고리즘을 활용해서 정리한다.
아래 활동을 통해서 정렬 알고리즘에 대해서 알아보도록 해보자.
정리되어 있지 않은 4장의 카드가 있다. 이 4장의 정리되지 않은 카드를 컴퓨터의 데이터라고 생각을 하고 작은 숫자부터 차례대로 정렬해보자.
첫째. 첫 번째 카드와 두 번째 카드를 비교해서 두 번째 카드가 더 작으면 서로 바꾸고, 아니면 그대로 둔다.
둘째. 첫 번째 카드와 세 번째 카드를 비교해서 세 번째 카드의 숫자가 더 작으면 서로 바꾼다.
셋째. 첫 번째 카드와 네 번째 카드를 비교해서 세 번째 카드의 숫자가 더 작으면 서로 바꾼다.
이러한 방법으로 두 번째 카드와 세 번째 카드, 두 번째 카드와 네 번째 카드, 세 번째 카드와 네 번째 카드를 비교해서 작으면 서로 바꾸면 작은 숫자부터 큰 숫자까지 정렬이 된다.
2지시문을 만들어서 카드 정리하기
친구와 함께 지시문을 보고 카드를 정리 할 수 있다.
숫자 카드, 노트, 필기구
1.카드는 학생들이 직접 만들어 활용할 수 있도록 한다.
2.학생들의 수준에 따라서 카드를 2~3장부터 시작해서 여러장으로 늘려서 활동할 수 있다.
3.활동이 익숙해지면 다양한 정렬 알고리즘을 활용해서 활동할 수 있도록 한다.
3보조활동
지시문을 보고 카드 정렬하기
지시문
숫자 카드, 지시문
4장의 카드를 골고루 섞고, 숫자가 보이지 않도록 뒤집은 후 한 번에 2장의 카드만 뒤집어 확인하고 지시문대로 수행한다.
10-1
숫자 카드와 지시문 만들기
게임을 하기 위한 숫자 카드와 지시문을 만들어 보자.
더 알아보기
정렬 알고리즘에 대해서 알아보자
정렬 알고리즘은 주어진 데이터를 순서에 따라 나열하는 것으로 이미 정렬된 리스트를 이용할 경우, 검색이 빠르게 이루어질 수 있어 검색을 위해 미리 알고리즘을 사용한다. 또한, 정렬 알고리즘은 데이터의 정규화나 의미 있는 결과물을 생성하는 데 유용하게 쓰인다.
1선택정렬
아래 그림과 같이, 선택정렬은 배열이 정렬되지 않은 부분에서 가장 작거나 큰 값을 찾은 다음, 배열이 정렬된 부분으로 옮기는 작업을 반복하는 정렬 방법이다.
2삽입 정렬
삽입 정렬은 가장 일반적인 정렬 기법 중 하나다. 카드게임이나 고스톱 게임에서 많이 사용되기도 한다. 예를 들어 일곱 장의 카드를 받았을 때 최초에는 내 손에 카드가 한 장도 없는 상태이다.
카드를 한 장 받으면 그것을 내 손에 쥐게 되고, 한 장이므로 이미 정렬된 상태이다. 두 번째 카드를 받으면 내 손에 이미 있는 카드와 비교하여 적절한 위치에 두고 마지막 7장 카드가 들어왔을 때도 이미 정렬된 6장의 카드와 비교하여 적절한 위치에 두어 카드 모두를 정렬시키는 방법이다. 이 방법을 이용해 손에 있는 모든 카드는 언제나 일정한 순서대로 정렬이 되어 있다.
3버블 정렬
버블 정렬은 배열의 첫 부분부터 순서대로 끝에 도달하면 다시 처음부터 계속 반복하여 인접한 두 원소가 올바른 순서가 되도록 교환하는 작업을 수행한다. 자료의 정렬만을 목적으로 한다면 많은 교환 횟수 때문에 기피되는 정렬 알고리즘이다. 사다리 타기 게임에서 가장 적은 가로줄로 특정한 결과를 얻을 때 활용할 수 있다.
<참고문헌>
1.교육부(2017). 언플러그드를 활용한 소프트웨어교육 2.국립특수교육원(2018). Fun! Fun! 언플러그드