[C/C++] 코드업(codeup) 3011번 거품 정렬(Bubble Sort)

▽문제 바로가기

https://codeup.kr/problem.php?id=3011

거품 정렬(Bubble Sort)

---

입력

첫 줄에 데이터의 개수 n이 입력된다. (2 <= n <= 1,000)

둘째 줄에 n개의 데이터가 공백을 기준으로 입력된다.

 

출력

정렬이 끝나는 단계를 출력한다.

 

문제 풀이

 

문제의 핵심을 파악해야 합니다. 문제의 핵심은 버블 정렬 중 어느 단계에서 정렬이 완료되었는지 찾는 문제입니다.

 

문제에서는 버블정렬의 속도 향상을 이야기했는데 정렬 여부를 파악하기 위해서는 결국 정렬된 데이터가 필요하다고 생각했습니다.(모순 같지만...)

 

입력이 1000 이하 이므로 제곱은 1,000,000으로 알고리즘 성능을 요구하는 문제가 아니라고 생각했습니다.

 

자 그러면 버블 정렬을 실행하면서 몇 번 정렬을 수행했는지 카운트해야하고 정렬이 완료 되었는지 확인해야 합니다.

 

1. 몇 번 정렬을 수행 했는지 카운트하기 위해서는 이중 반복문 중 안쪽 반복문이 실행 완료 후 count++ 할 수 있습니다.(정렬이 완료된 데이터가 입력되지는 않습니다.)

 

2. 정렬이 완료되었는지 확인하기 위해서는 안쪽 반복문 실행 때마다 j인덱스 위치에 정렬이 되었는지 확인합니다. 정렬이 되었다면 체크 카운트를 1 증가시킵니다.(check++)

 

버블 정렬은 큰 값을 뒤쪽으로 보내면서 오름차순으로 정렬하기 때문에 만약 바깥쪽 반복문이 i번수행 되었다면 이미 i의 수만큼 배열이 완료되었다는 뜻입니다. 따라서 전체 배열 갯수가 a라고 한다면

check==a-1-i 식을 만족하면 정렬이 완료되었다는 의미입니다.

 

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

using namespace std;

int main() {
    
    int a;	//배열갯수 
    scanf("%d", &a);
    //입력받을 벡터
    vector <int> arr(a);
    for(int i=0;i<a;++i){
    	scanf("%d", &arr[i]);
    }
    //입력받은 벡터를 복사한 벡터
    vector <int> arr2(arr);
    //복사한 벡터를 올림차순으로 정렬
    sort(arr2.begin(), arr2.end());
    int count = 0;
    
    for(int i=0;i<arr.size()-1;++i){
    	int check=0;
    	for(int j=0;j<arr.size()-i-1;j++){
    		if(arr[j]>arr[j+1]){
    			int temp = arr[j];
    			arr[j] = arr[j+1];
    			arr[j+1] = temp;
    		}
    		//j위치가 정렬된 수만큼 check증가
    		if(arr[j]==arr2[j]) check++;
    	}
    	count++;	//정렬횟수증가(안쪽 반복문 완료후) 
    	//정렬이 완료되었다면 반복문중지
    	if(check==a-1-i&&arr[a-1]==arr2[a-1]) break;
    }
    
    //정렬횟수 출력
    printf("%d\n", count);
    
        
    return 0;
}