[it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비] 정렬 - 버블정렬

문제

N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
정렬하는 방법은 버블정렬입니다.

💡 입력설명
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다. 두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

💡 출력설명
오름차순으로 정렬된 수열을 출력합니다.

💡 입력예제
6
13 23 11 7 5 15

💡 출력예제
5 7 11 13 15 23

 

---

코드

최종 풀이

#include <stdio.h>
#include <vector>

using namespace std;

int main() {
	int n, i, j, tmp;
	scanf("%d", &n);
	vector<int> a(n);
	for(i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	for(i = 0; i < n - 1; i++) {
		for(j = 0; j < n - i - 1; j++) {
			if(a[j] > a[j + 1]) {
				tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
			}
		}
	}
	for(i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
	return 0; 
}

 

---

설명

사용자로 부터 N을 입력받고 N만큼 반복하는 for문을 작성하여 자연수를 입력받고 a배열에 할당한다.

a배열에서 0부터 n-1까지 순회(마지막 부분 제외)하고 해당 a배열에서 0부터 n-i-1까지 반복하는 2중 for문을을 작성한다.

해당 배열과 다음 배열을 비교했을 때 a[j+1](다음 배열)이 a[j]보다 작을 경우 둘을 swap해나가며 둘 중 작은 값을 앞으로 배치시켜나간다.

 

---

배운 점

버블정렬

개념

서로 인접한 두 원소를 비교하여 swap하면서 정렬하는 알고리즘 기법이다. (원소의 이동이 거품처럼 수면에 올라오는 모습이여서 지어졌다고 한다.)

 

 

시간복잡도

(n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2이므로, O(n^2) 이다.

 

공간복잡도

하나의 배열 안에서 swap이 이루어지며 정렬이 되므로 O(n)이다.

 

장점

1. 구현이 간단하다.

2. 다른 메모리 공간이 필요하지 않다.

 

단점

1. 시간복잡도가 좋지 않아 비효율적이다.

2. 불필요한 swap이 많이 발생한다.

---

 

해당 내용은 김태원님의 'it 취업을 위한 알고리즘 문제풀이' 강의를 듣고 작성한 글입니다.