정보처리기사 실기시험에 조금이나마 도움이 드리고자 올립니다. 수험을 보시는 분들의 좋은 성과가 있기를 바랍니다.^^
오늘은 정보처리기사에서 이미 출제가 된 적이 있는 버블 정렬 알고리즘에 관해서 살펴보려고 합니다. 대표적인 정렬 알고리즘에는 삽입 정렬, 퀵 정렬, 선택 정렬, 버블 정렬이 있습니다.
이외에도 무수히 많은 정렬 알고리즘이 있습니다. 그중에서 우리는 버블 정렬에 관해서 알아보겠습니다.
버블정렬이란
인접한 두 값을 비교하여 정렬하는 방법입니다. 한쪽에서 다른 한쪽으로 크기를 비교, 교환함으로써 반대편까지 가게 되면 가장 큰 값, 또는 가장 작은 값이 한쪽 끝으로 이동하게 됩니다. 이러한 비교, 교환 과정으로 모든 데이터가 정렬될 때까지 반복합니다. 이동 과정이 마치 물속의 거품(bubble)과 같이 보글보글 떠오르는 모습과 유사하여 버블 정렬이라고 합니다.
아~하.. 이런 개념이 있군요^^
그럼 한번 순서도를 보면서 알아볼까요?
순서도
역시나 순서도는 그림판으로 작성하였습니다. 허접해도… 이해해 주시길^^;;
솔직히 말해서 알고리즘은 그렇게 복잡하지 않습니다. 저도 이걸 한 10분 정도 본 후에 파악했으니깐요..
간단하게 설명을 드리면, N=10 경우에는 배열에 데이터 총 저장 개수입니다. 그 외에 변수들 FLAG, Q, J 같은 경우에는 분기점에서 조건을 만족시킬 경우에 YES, NO를 나누기 위한 것입니다.(즉 버블 정렬은 인접한 놈들이랑 교환하는데요, 5,2,1,3 이렇게 있다면 하나씩 비교해 보는 과정을 그리기 위해서 FLAG, Q, J의 변수를 사용합니다)
중요한 것은 중간에 있는 교환하는 부분입니다. 설명을 굳이 안 해도 서로 데이터가 교환된다는 것을 알 겁니다. A(J) 자리에는 A(J+1) 자리에 있는 값을 저장하고, A(J+1) 자리에는 A(J) 값을 저장하게 됩니다.
이 부분이 가장 핵심인 거죠. 그럼 코딩을 한번 볼까요?
C언어코딩
부가적인 설명은 주석을 통해서 달아놓았습니다. 설명이 조금 어설픈가요?^^;
결론은 이중 while 문을 사용해서 짰습니다. 그 외에는 순서도에 있는 부분을 그대로 옮겨놓았다고 보시면 됩니다. 굉장히 간단한 작업이었는데, 이 부분이 은근히 생각 외로 시간을 투자했네요..
결과
결과를 보시면 아시겠지만, 임의의 데이터를 마구잡이로 입력하였지만, 출력은 1~10까지 정상적으로 출력되는 모습을 볼 수 있습니다.
조금 더 응용해서 프로그램을 짜보려고 하였지만, 코드 길이만 길어지고, 시간을 많이 투자할 것 같다는 생각이 들었습니다. 무엇보다 핵심은 알고리즘이니깐요 ㅎ