알고리즘과 버블정렬 정리

• 알고리즘은 문제를 풀기 위한 여러 동작의 모임이며 유한성을 가져 언젠가는 끝나야 한다.
• 버블정렬은 인접한 두 원소를 비교해 순서가 맞지 않으면 교환하며 한 회전마다 가장 큰 값이 뒤로 이동한다.
• 비교 횟수는 N(N-1)/2이고 수행 시간은 O(N^2)이라 성능이 낮아 주로 교육용으로 쓰인다.

알고리즘의 개념과 설계 기법

• 알고리즘은 문제를 풀기 위한 여러 동작의 모임이며 유한성을 가져 언젠가는 끝나야 한다는 속성이 있다.
• 수학과 컴퓨터와 과학 분야에서 작동이 이루어지도록 하는 단계적 집합이며 연산과 데이터 처리와 자동화된 추론을 수행한다.
• 자료 구조로 보면 배열과 연결리스트와 큐와 스택으로 이루어진 선형구조와 트리와 그래프로 이루어진 비선형 구조가 있다.
• 문제와 조건이 다양해 일반적인 설계 방법론은 없지만 분할정복과 욕심쟁이 방법과 동적 프로그래밍이 대표 기법이다.
• 일상의 예로 자판기에서 음료를 뽑는 과정, 곧 앞으로 가서 돈을 넣고 버튼을 선택하고 음료와 잔돈을 받는 순서도 알고리즘이다.
• 알고리즘은 어떤 일을 해결하려 할 때의 절차 과정이라고 보면 쉽다.
• 알고리즘을 얼마나 많이 아는가보다 문제에 접근해 해결하는 과정, 곧 문제해결능력과 개발 요령이 더 중요하다고 강조한다.
• 짧고 쉽게 설명하면서도 구현이 까다로운 문제가 많아 알고리즘이 면접용 코딩 문제로 많이 쓰인다고 설명한다.

버블정렬의 원리와 분석

• 버블정렬은 서로 인접한 두 원소를 검사해 순서가 맞지 않으면 교환하는 알고리즘으로 선택정렬과 개념이 비슷하다.
• 첫째와 둘째 자료를, 다음에는 둘째와 셋째 자료를 비교하는 식으로 끝까지 가면 1회전이 끝나고 가장 큰 자료가 맨 뒤로 간다.
• 회전을 거듭할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.
• 여덟 개 숫자 예제에서는 5와 1을 바꾸고 7과 4를 바꾸는 식으로 처음부터 반복해 마지막에 1에서 8까지 정렬된다.
• 비교 횟수는 N(N-1)/2번이고 평균 교환 횟수는 N(N-1)/4번이며 수행 시간은 O(N^2)이다.
• 바깥 반복문이 약 N단계이고 안쪽 반복문도 약 N단계라 곱하면 N 제곱 시간이 걸린다.
• 장점은 알고리즘이 간단하고 플래그를 쓰면 효율적으로 수행할 수 있다는 점이다.
• 단점은 이미 정렬된 자료도 최소 1회전은 돌아야 하고 이미 비교한 원소를 또 비교해 비효율적이라 주로 교육용으로 쓰인다는 점이다.

버블정렬 분석

핵심 개념

• 알고리즘 — 문제를 풀기 위한 여러 동작의 모임으로 유한성을 가지며 언젠가는 끝나는 절차이다.
• 버블정렬 — 인접한 두 원소를 비교해 순서가 맞지 않으면 교환하며 정렬하는 알고리즘이다.
• 시간복잡도 — 입력 크기에 따라 수행 시간이 늘어나는 정도로 버블정렬은 O(N^2)으로 표기한다.
• 선형구조 — 배열과 연결리스트와 큐와 스택으로 이루어진 자료 구조를 가리킨다.

자주 묻는 질문

• Q. 버블정렬은 어떻게 동작하나?
  A. 첫째와 둘째, 둘째와 셋째 자료를 차례로 비교해 순서가 맞지 않으면 바꾸며 한 회전이 끝날 때마다 가장 큰 자료가 맨 뒤로 이동한다.
• Q. 버블정렬은 왜 비효율적이라고 하나?
  A. 비교와 교환 횟수가 많아 수행 시간이 O(N^2)이고 이미 정렬된 자료도 최소 한 번은 전체를 돌아야 하기 때문이다.
• Q. 알고리즘을 왜 배워야 하나?
  A. 일상과 개발의 문제를 해결하는 절차를 논리적으로 기술하는 능력을 키우고 문제해결능력과 개발 요령을 기르는 바탕이 되기 때문이다.

정리

알고리즘은 문제 해결 절차를 논리적으로 나타낸 것이며 버블정렬은 단순하지만 비효율적이어서 교육용으로 이해하기에 적합하다고 정리한다.