7231 : 안정 정렬 확인
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
안정 정렬(Stable Sort)은 동일한 키를 가진 원소들의 상대적 순서를 보존하는 정렬입니다.
카드 묶음을 숫자 기준으로 버블 정렬과 퀵 정렬로 각각 정렬한 후, 동일한 숫자를 가진 카드들의 문양 순서가 입력 순서와 일치하는지 확인하십시오.
Python의
[제약 조건]
• 입력되는 모든 수는 정수입니다.
카드 묶음을 숫자 기준으로 버블 정렬과 퀵 정렬로 각각 정렬한 후, 동일한 숫자를 가진 카드들의 문양 순서가 입력 순서와 일치하는지 확인하십시오.
Python의
sorted()는 안정 정렬을 보장합니다.[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 원소의 개수 $N$이 주어집니다. ($1 \le N \le 10{,}000$)
둘째 줄부터 $N$개의 줄에 카드 문양(H, D, S, C)과 숫자(1~13) 쌍이 주어집니다.
둘째 줄부터 $N$개의 줄에 카드 문양(H, D, S, C)과 숫자(1~13) 쌍이 주어집니다.
출력 설명
버블 정렬 결과의 안정성을
이어서 버블 정렬 결과를 한 줄에 하나씩 출력합니다.
퀵 정렬 결과의 안정성을
이어서 퀵 정렬 결과를 한 줄에 하나씩 출력합니다.
Bubble: Stable 또는 Bubble: Unstable로 출력합니다.이어서 버블 정렬 결과를 한 줄에 하나씩 출력합니다.
퀵 정렬 결과의 안정성을
Quick: Stable 또는 Quick: Unstable로 출력합니다.이어서 퀵 정렬 결과를 한 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
H 3
D 3
S 1
C 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
Bubble: Stable
S 1
H 3
D 3
C 3
Quick: Stable
S 1
H 3
D 3
C 3도움
원래 인덱스를 함께 저장하여 정렬 후 같은 숫자에서 인덱스 순서가 유지되는지 확인합니다. Python의
sorted()는 안정 정렬이지만, 직접 구현하는 퀵 정렬은 안정적이지 않을 수 있습니다.