Algorithm 공부 #05 - 정렬(버블 정렬과 선택 정렬)

 

Algorithm 공부 #05 - 정렬(버블 정렬과 선택 정렬)

 

정렬

    데이터를 정해진 기준에 따라 배치에 의미 있는 구조로 재설정하는 것

   

      ● 버블 정렬 (Bubble Sort) : 데이터의 인접 요소끼리 비교하고 swap연산을 수행하며 정렬

      ● 선택 정렬 (Selection Sort) : 대상에서 가장 크거나 가장 작은 데이터를 찾아가 선택을 반복하면서 정렬

      ● 삽입 정렬 (Insertion Sort) : 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하며 정렬

      ● 퀵 정렬 (Quick Sort) : pivot값을 선정해 해당 값을 기준으로 정렬

      ● 병합 정렬 (Merge Sort) : 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬

      ● 기수 정렬 (Radix Sort) : 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬

 

 

버블 정렬(Bubble Sort)

    ● 두 인접한 데이터의 크기를 비교해 정렬하는 방법으로 간단하게 구현할 수 있지만 O(n^2)의 시간 복잡도를 가짐

    ● 루프를 돌면서 인접한 데이터 간의 swap연산으로 정렬

    ● 버블 정렬 과정       

        1. 비교 연산이 필요한 루프 범위를 설정

        2. 인접한 데이터 값을 비교

        3. swap조건에 부합하면 swap연산

        4. 루프 범위가 끝날 때까지 2~3을 반복

        5. 정렬된 영역을 설정 후 다음에 정렬할 때는 이 영역을 제외

        6. 비교 대상이 없을때까지 1~5를 반복

 

 

예제

    백준 2750번 수 정렬하기

     https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

※  N이 1000이하이므로 시간 복잡도가 O(n^2)인 버블 정렬을 사용해도 무관 ※

ㅍㅊㄹ루ㅛ52ㄱㅎ

#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>A(N, 0);

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

	for (int i = 0; i < N-1; i++) {
		for (int j = 0; j < N - 1 - i; j++) {
			if (A[j] > A[j+1]) // 인접한 값끼리 비교
				swap(A[j], A[j+1]); // swap 연산
		}
	}

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

 

 

백준 1377번 버블 소트

https://www.acmicpc.net/problem/1377

1377번: 버블 소트

 

 

※ false일 때 출력되기 위해서는 버블 정렬 중 swap이 한 번도 일어나지 않은 루프가 언제인지 알아내는 게 핵심 ※

● 이중 for문을 다 돌리기에는 N의 값이 크기 때문에 버블 정렬로 풀면 시간 초과가 발생할 수 있음

● vector를 생성해 pair쌍으로(입력값, 인덱스) push해주고 sort알고리즘을(O(nlogn)) 통해 vector를 정렬

● 정렬 전 인덱스와 정렬 후 인덱스를 비교하여 최댓값을 찾은 후 +1(swap이 일어나지 않는 반복문이 한 번더 실행)

 

#include<iostream>
#include<algorithm>
#include<vector>
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++) {
		int x;
		cin >> x;
		A[i].first = x; 
		A[i].second = i; 
	}

	sort(A.begin(), A.end()); // O(nlogn)의 시간 복잡도
	int max = 0;

	for (int i = 0; i < N; i++) {
		int temp = A[i].second - i; // 정렬 전 인덱스와 정렬 후 인덱스의 차이
		if (max < temp)
			max = temp;
	}

	cout << max + 1;
}

 

 

 

선택 정렬(Selection Sort) 

    ● 대상 데이터에서 최소나 최대 데이터를 나열된 순으로 찾아가며 선택하는 방법

    ● 구현 방법이 복잡하고, 시간 복잡도도 O(n^2)으로 효울적이지 않아 코테에서는 많이 사용되지 않음

    ● 선택 정렬 과정       

        1. 남은 정렬 부분에서 최솟값 또는 최댓값을 찾기

        2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap하기

        3. 가장 앞에 있는 데이터의 위치를 변경해(index++) 남은 정렬 부분의 범위를 축소

        4. 전체 데이터 크기만큼 index가 커질 때까지, 남은 정렬 부분이 없을 때까지 반복

 

예제

  백준 1427번 수 정렬하기

https://www.acmicpc.net/problem/1427

1427번: 소트인사이드

 

※ N이 매우 크기 때문에 string입력 받은 후 데이터를 정수로 바꿔서 벡터에 저장 ※

  ● 배열의 데이터를 선택 정렬 알고리즘을 이용해 내림차순 정렬

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

int main() {

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

	string A;
	cin >> A;

	int N = A.length();
	vector<int>arr(N, 0);

	for (int i = 0; i < N; i++) {
		int n = A[i] - '0';
		arr.push_back(n);
	}

	for (int i = 0; i < N; i++) {
		int max = i;
		for (int j = i + 1; j < N; j++) {
			if (A[max] < A[j])
				max = j; // 최댓값 찾기
		}

		if (A[i] < A[max])
			swap(A[i], A[max]);
	}
	for (int i = 0; i < N; i++)
		cout << A[i];
}