맨 앞 인덱스부터 기준이 된다. 기준보다 뒤에 있는 값들을 기준과 비교하면서 기준보다 작을 경우 기준과 해당 값을 swap해준다. swap 후에는 기준이 그 다음 인덱스로 바뀐다.
a=[4,7,1,3,5,2]
for i in range(len(a)-1):
for j in range(i+1,len(a)):
if a[i]>a[j]:
a[i],a[j]=a[j],a[i] # swap
for i in range(len(a)):
print(a[i],end=' ')
O(N^2)
의 시간 복잡도를 가짐)버블 정렬은 첫번째 원소부터 인접한 원소와 비교하며 자리를 바꾸면서 맨 끝부터 정렬하는 방식이다.
a = [8, 3, 12, 10, 1]
for i in range(len(a)-1,0,-1): # 4 3 2 1
for j in range (0,i): # i가 4일때 0 1 2 3
if a[j]>a[j+1]:
a[j],a[j+1]=a[j+1],a[j]
O(N^2)
의 시간 복잡도를 가진다.새로운 배열에 값을 하나씩 삽입하여 마지막부터 직전의 값과 비교하여 정렬하는 알고리즘이다. 버블정렬의 비교 횟수를 줄이기 위해 고안된 정렬이다. 비교 대상이 정렬되어 있을 경우 비교를 하지 않아도 된다.
a=[4,7,1,3,5,2]
result=[]
for i in range(len(a)):
result.append(a[i]) # 삽입
for j in range(i,0,-1): # 뒤 -> 앞
if result[j-1]>result[j]: # 현재 vs 직전값 비교
result[j],result[j-1]=result[j-1],result[j]
else:
break
O(N^2)
의 시간 복잡도를 가진다.계수 정렬은 요소들을 비교하지 않고 요소들의 개수를 세어서 정렬하는 방식이다. 이 때문에 계수 정렬을 셈 정렬이라고도 한다.
n=int(input())
a=list(map(int,input().split())) # 1~100사이의 숫자들을 받음
bucket=[0]*101
# dat 등록
for i in range(n):
bucket[a[i]]+=1
# 누적합 구하기
for i in range(1,len(bucket)):
bucket[i]+=bucket[i-1]
# bucket[i]=bucket[i]+bucket[i-1]
# 값넣기
result=[0]*101
for i in range(n):
index=a[i]
result[bucket[index]-1]=a[i]
bucket[index]-=1
for i in range(n):
print(result[i],end=' ')
O(N)
의 효율적인 시간 복잡도를 가지게 된다.