버블 정렬 Bubble Sort

박선우·2022년 9월 19일
0

Algorithm

목록 보기
1/1
post-thumbnail

버블 정렬


정렬이란

  • 임의의 자료 집합을 일정한 기준에 따라 나열하는 것이다.
  • 자료의 작은 것을 먼저 나열하는 것을 오름차순이라고 한다.
  • 자료의 큰것을 먼저 나열하는 것을 내림차순이라고 한다.
  • 정렬의 원리는 레코드의 키들을 비교해보고 순서를 바꿀 필요가 있는 레코드를 정렬이 완료될 때 까지 반복한다.
  • 가장 간단한 정렬 알고리즘이 버블 정렬이다.
  • 버블 정렬은 레코드의 선두부터 인접 요소를 비교하여
    큰 값을 뒤로 보내는 방식으로 정렬한다.

버블정렬 알고리즘 문제

선생님은 학생들을 모두 앞으로 나오게 하여 무작위로 일렬로 세웠다.
키가 들쑥날쑥하여 일정하지 않다.
이제 선생님은 이 학생들의 키를 재고, 키 순서대로인 오름차순으로 번호를 부여하려 한다.

프로젝트를 생성하여 다음의 과정을 거쳐서 키 순서대로 만드는 알고리즘을 작성해보자.

입력한 키 데이터들이, 교환이 수행될 때마다 현재의 키 데이터의 순서를 출력한다.

입력

  • 입력할 키 데이터를 프로그램 콘솔 키보드로부터 입력 받는다.
  • 입력할 키 데이터는 정수형으로 6개만 입력한다.

출력

  • 입력한 키 데이터에 따른 정렬 결과를 프로그램 콘솔 터미널에 출력한다.
  • 입력한 키 데이터들이 교환이 수행될 때마다 현재의 키 데이터의 순서를 출력한다.

실행예시

TestCase는 다음과 같다.

입력값 : 143 134 137 132 140 134

다음과 같이 출력한다.


한 줄, 한 줄 해보기

#include <iostream>
using namespace std;

void bubble(int* pArr, int num) {
	cout << "정렬 시작" << endl;
	for (int x = 0; x < num - 1; x++) {
		for (int i = x; i < num - 1; i++) {
			int temp = 0;
			if (pArr[i - x] > pArr[i - x + 1]) {
				temp = pArr[i - x];
				pArr[i - x] = pArr[i - x + 1];
				pArr[i - x + 1] = temp;
			}
		}
		for (int i = 0; i < num; i++) {		     // 교환 과정 출력
			cout << pArr[i] << " ";
		}
		cout << endl;
	}
	cout << "정렬된 키 순서" << endl;
	for (int i = 0; i < num; i++) {
		cout << pArr[i] << " ";
	}
}

void main() {
	int* height = 0;
	int num = 0;
	cout << "학생 수를 입력하세요." << endl;		// 배열의 길이 입력
	cin >> num;
	height = new int[num];
	for (int i = 0; i < num; i++) {
		height[i] = 0;
	}
	cout << "학생들의 키를 입력하세요." << endl;	// 키 데이터 입력
	for (int i = 0; i < num; i++) {
		cin >> height[i];
	}
	cout << "입력된 학생들의 키" << endl;			// 입력된 값 확인
	for (int i = 0; i < num; i++) {
		cout << height[i] << " ";
	}
	cout << endl;

	bubble(height, num);
	delete[] height;
}

문제에서는 정수형 데이터 6개를 입력하게 했지만,
역시 일반화 시키는게 재밌을 것 같아서 배열의 길이를 입력받도록 해봤다.
정리하다보니 잘... 해보면 데이터 개수를 미리 입력받지 않고,
무작위로 데이터를 입력한 뒤에 배열의 길이를 잴 수 있지 않았을까?

profile
한 줄, 한 줄

0개의 댓글