글 읽기 - 버블쏠트에서 sort와 stable

joseph415 5년 전 0

아래 코드가 계속 틀린값이 나와서 혹시나 해서 stable_sort로

바꿔봤는데 정답이 나오더라구요 이게 왜 차이가 나는거죠?

버블솔트는 같은값이면 안바뀌니까 안정정렬이구

그냥 sort는 같은 값이여도 정렬해주나요??

#include <iostream>
#include <algorithm>
using namespace std;
struct a{
    int n;
    int c;
};
bool compare(const a &p1,const a &p2){
    return p1.n<p2.n;
}
int main() {
    int n;
    cin >> n;
    struct a a[500000];
    for (int i = 0; i < n; i++) {
        cin >> a[i].n;
        a[i].c = i;
    }
    sort(a,a+n,compare);   //stable_sort는 정답
    int k=0;
for(int i=0;i<n;i++){
    if(k<a[i].c-i) {
        k = a[i].c - i;
    }
}
    cout<<k+1<<'\n';
}

joseph415 5년 전 0

어느경우에서 차이가 나는질 모르겠습니다.ㅠ

bupjae 5년 전 1

BOJ 문제에 대한 질문을 올릴 때에는 문제 번호를 같이 써 주세요. BOJ에는 버블 정렬에 관한 문제가 적어도 5개 있습니다.

입출력 형식 및 작성한 알고리즘을 봤을 때 1377번 또는 1517번 문제인 것으로 보이므로 그걸 기준으로 설명하겠습니다.

정렬에서 "stable" 이라 함은 "동등한" 두 원소 a, b 가 있고 (compare(a, b) == false 와 compare(b, a) == false 를 만족하는 두 원소 a, b)

정렬 전 배열에서 a가 앞에 있고 b가 뒤에 있었다면

정렬 후 결과 또한 a가 앞에 있고 b가 뒤에 있는 것이 보장되는 정렬 방법을 의미합니다.

버블 정렬은 stable 이 보장되는 정렬 방법입니다. 따라서 이 문제를 푸는 알고리즘 또한 stable 이 보장되는 정렬 알고리즘을 사용해야 합니다.

bupjae 5년 전 1

또는, compare 함수에서 n 이 같으면 c 를 비교한 결과를 반환하도록 한다면, 서로 다른 위치에 있었던 같은 값은 더 이상 "동등한" 관계가 아니므로

stable 이 아닌 정렬 방법을 사용해도 항상 올바른 결과를 계산할 수 있게 됩니다.

joseph415 5년 전 0

@bupjae

항상 댓글달아주셔서 감사합니다 잘 이해되었습니다.!👍

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

버블쏠트에서 sort와 stable_sort질문입니다

joseph415 5년 전 0

joseph415 5년 전 0

bupjae 5년 전 1

bupjae 5년 전 1

joseph415 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말