[Do it! 알고리즘 코딩테스트: Chapter 4] 버블 정렬(Bubble Sort), 선택 정렬(Selection sort)

본 포스팅은 Do it! 알고리즘 코딩테스트: C++편을 토대로 공부한 내용을 정리하기 위한 포스팅입니다.

https://github.com/KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp

GitHub - KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp: Do it! 알고리즘 코딩 테스트: C++편

 

1. 버블 정렬 (Bubble Sort)

인접한 두 원소를 비교하여 교환하는 방식으로 정렬하는 알고리즘이다.
큰 값이 점점 뒤로 이동하는 모습이 거품이 떠오르는 것과 비슷해서 "버블 정렬"이라고 한다.

 

• 동작 방식
  1. 첫 번째 원소부터 인접한 원소끼리 비교하여 큰 값을 뒤로 이동한다.
  2. 한 바퀴 돌면 가장 큰 값이 맨 뒤로 정렬된다.
  3. 다음 라운드에서 마지막 정렬된 원소를 제외하고 반복한다.
  4. 배열이 정렬될 때까지 반복한다.
• 시간 복잡도
  • 최선: O(n) (이미 정렬된 경우)
  • 평균: O(n^2)
  • 최악: O(n^2)
• 특징
  • 구현이 쉽지만, 효율이 낮아 실제로는 잘 사용되지 않는다.
  • 안정 정렬(Stable Sort)이다.

 

// Baekjoon Online Judge Problem. 2750
#include <iostream>
#include <vector>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	vector<int> myVector(N, 0);

	for (int i = 0; i < N; i++) {
		cin >> myVector[i];
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N - i - 1; j++) {
			if (myVector[j] > myVector[j + 1]) {
				int temp = myVector[j];
				myVector[j] = myVector[j + 1];
				myVector[j + 1] = temp;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		cout << myVector[i] << '\n';
	}

	return 0;
}

 

 

 

// Baekjoon Online Judge Problem. 1377
#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;
    vector<pair<int, int>> A(N);

    for (int i = 0; i < N; i++) {
        cin >> A[i].first;
        A[i].second = i;
    }

    sort(A.begin(), A.end());
    int max = -1;

    for (int i = 0; i < N; i++) {
		
        if (max < A[i].second - i) {
            max = A[i].second - i;
        }
	}

    cout << max + 1<< '\n';

	return 0;

}

 

 이 문제의 핵심은 swap을 통해 데이터가 왼쪽으로 이동할 수 있는 최대 거리가 1이라는 점을 캐치하는 것이었다. 따라서 for문을 몇 번 이동했는지는 정렬 전 index와 정렬 후 index의 차이에 1을 더한 값과 같다. 버블 정렬로 문제를 해결하면 시간 복잡도가 O(n^2)이 돼서 시간 초과가 걸리게 된다. 하지만 <algorithm> 라이브러리의 sort() 함수를 사용하면 시간 복잡도가 O(nlogn)이 되므로 해결할 수 있게 된다.

 

 문제를 해결하기 위해서는 vector 변수에 2가지 이상의 정보를 저장할 수 있어야 했다. 이를 위해서는 struct, pair, tuple 중 한 가지를 사용해야 한다. 문제에서는 pair를 사용했다. 아직 vector 라이브러리에 미숙해서 이런 자료들이 있는지 몰랐고 어떻게 적용하는지도 잘 몰라서 검색을 많이 했다. C++ 언어 공부도 열심히 해야겠다. 

 

#include<utility> // pair의 헤더파일

 

 pair class는 utility 헤더파일에 존재하는 STL이다. 하지만 vector, alogrithm 헤더파일에 이미 utility 헤더파일이 포함되어 있기 때문에 굳이 포함 할 필요는 없다.

 

template <class T1, class T2> struct pair;

#include<iostream>
#include<vector>
using namespace std;

pair<int, double> p;

int main() {

    vector<pair<int, int>> vec; // vector와 pair를 함께 사용

    p.first = 5; // pair의 첫번째 인자에 접근
    p.second = 10; // pair의 두번째 인자에 접근
    p = make_pair(1, 2.1); // make_pair
    
    return 0;
}

 

 

2. 선택 정렬 (Selection Sort)

가장 작은 원소를 선택하여 맨 앞부터 차례로 정렬하는 방식이다.

• 동작 방식
  1. 주어진 리스트에서 최솟값을 찾는다.
  2. 최솟값을 맨 앞 원소와 교환한다.
  3. 나머지 리스트에서 다시 최솟값을 찾아 두 번째 원소와 교환한다.
  4. 이 과정을 리스트 끝까지 반복한다.
• 시간 복잡도
  • 최선: O(n^2)
  • 평균: O(n^2)
  • 최악: O(n^2)
• 특징
  • 비교 횟수가 많아 비효율적이다.
  • 불안정 정렬(Unstable Sort)이다.

 

// Baekjoon Online Judge Problem. 1427

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string str;
	cin >> str;
	vector<int> v(str.size(), 0);

	for (int i = 0; i < str.size(); i++) {
		v[i] = str[i] - '0';
	}

	for (int i = 0; i < str.size(); i++) {
		pair<int, int> max;
		max.first = v[i];
		max.second = i;

		for (int j = i; j < str.size(); j++) {
			if (max.first < v[j]) {
				max.first = v[j];
				max.second = j;
			}
		}

		int temp = v[i];
		v[i] = max.first;
		v[max.second] = temp;
		
	}

	for (int i = 0; i < str.size(); i++) {
		cout << v[i];
	}

	return 0;
}