[1377] 버블 소트 (정렬 인덱스, 안쪽 for문 실행 횟수, swap)

1377번: 버블 소트

 

분석

• 버블 정렬의 swap이 한 번도 일어나지 않은 루프가 언제인지 알아내는 문제
• 버블정렬의 이중 for 문에서 안쪽 for 문 전체를 돌 때 swap이 일어나지 않았다 == 이미 모든 데이터가 정렬됐다
•  N은 500,000보다 작거나 같은 자연수 : n^2불가
• 안쪽 루프는 1에서 n-j까지 swap 수행, 특정 데이터가 안쪽 루프에서 swap의 왼쪽으로 이동할 수 있는 최대 거리가 1이므로 데이터의 정렬 전 인덱스와 정렬 수 인덱스를 비교해 왼쪽으로 가장 많이 이동한 값을 찾아서 해결

bool changed = false;
for (int i=1; i<=N+1; i++) {
    changed = false;
    for (int j=1; j<=N-i; j++) {
        if (A[j] > A[j+1]) {
            changed = true;
            swap(A[j], A[j+1]);
        }
    }
    if (changed == false) {
        cout << i << '\n';
        break;
    }
}

 

풀이

"""N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.
버블소트 j for문에서 swap되지 않은 i찾기 : 전부 정렬 되었을 때의 i
N(1~500,000) n^2불가
"""
import sys
input=sys.stdin.readline

n=int(input())
a=[]
for i in range(n):
    a.append((int(input()),i))  # (val,idx)

soredA=sorted(a)
# print(a)
# print(soredA)

max=0
for i in range(n):
    if max<soredA[i][1]-i:
        max=soredA[i][1]-i

print(max+1)  # swap이 일어나지 않는 반복문 한번 더 실행됨으로 +1