백준 2750번: 수 정렬하기-파이썬(python)

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

---

n=int(input())
list=[]
for i in range(n):
  list.append(int(input()))
tmp=0
#버블정렬 사용해보자
for i in range(len(list)):
  for j in range(i+1,len(list)):
    if list[i]>list[j]:
      tmp=list[i]
      list[i]=list[j]
      list[j]=tmp
 
for i in range(len(list)):
  print(list[i])
 

-버블 정렬 활용

-서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
선택 정렬과 기본 개념이 유사하다.
버블 정렬(bubble sort) 알고리즘의 구체적인 개념
버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.
1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

버블정렬은 n**2의 시간복잡도를 가진다.