[python] 백준 2750번 수 정렬하기1 : 버블 정렬(BubbleSort) 향상시키기

 

문제 )

2750번: 수 정렬하기

 

 

알고리즘)

[알고리즘] 버블정렬 향상 시키기

 

코드)

1) 교환횟수 카운트하여 버블정렬 향상시키기 

N = int(input())
sortArr = []

for i in range(N) :
  sortArr.append(int(input()))

#버블정렬 시작!
for i in range(N) :
  changeCount = 0 # 교환횟수 변수
  for j in range(N-1,i,-1) :
    if sortArr[j] < sortArr[j-1] : # 오름차순
      sortArr[j], sortArr[j-1] = sortArr[j-1], sortArr[j]
      changeCount += 1 # 교환횟수 카운트
  if changeCount == 0 : # 교환횟수가 0이면 모두 정렬되었음을 의미하니 버블정렬 종료
    break

#출력
for i in range(len(sortArr)) :
  print(sortArr[i])

 

 

2) 마지막 교환한 인덱스 기억하여 버블정렬 향상시키기

N = int(input())
sortArr = []

for i in range(N) :
  sortArr.append(int(input()))

# 버블정렬 시작
for i in range(N) :
  lastIndex = 0 # 마지막 교환인덱스 변수
  for j in range(N-1,i,-1) :
    if sortArr[j] < sortArr[j-1] : #오름차순
      sortArr[j], sortArr[j-1] = sortArr[j-1], sortArr[j] 
      lastIndex = j # 교환이 발생한 인덱스 저장
  i = lastIndex # 마지막 교환이 발생한 인덱스부터 정렬하여 버블정렬 향상시키기
  
# 출력
for i in  range(n) :
  print(sortArr[i])