문제풀이/Sorting

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

IT록흐 2023. 4. 5. 15:05
반응형

 

문제 )

 

2750번: 수 정렬하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

www.acmicpc.net

 

 

알고리즘)

 

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

버블정렬은 가장 쉽고 이해하기 쉬운 정렬이다. 그러나 시간복잡도가 O(n2)이어서 효율이 좋지 않다. 7개의 수를 일차원 배열에 저장하였다. 이제 버블정렬을 사용하여 오름차순으로 바꾸어 보자

lordofkangs.tistory.com

 

코드)

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])

 

 

 

 

반응형