[알고리즘] 버블 정렬 (Python)

Do it! 알고리즘 코딩테스트: 파이썬 편과 자료구조 과목 학습 후 정리한 포스팅 입니다.

 

 

이번 포스팅에서는 버블 정렬에 대해 학습합니다.

 

I) 버블 정렬 이론

버블 정렬은 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식이다.시간 복잡도는 O(n^2)으로 다른 정렬 알고리즘보다 느리다

 

loop를 돌면서 인접한 데이터 간의 swap 연산으로 정렬한다. -> loop를 1번 돌 때 1개의 위치가 결정된다.특정 loop 전체에서 swap이 1번도 발생하지 않았다면 데이터가 모두 정렬되었다는 뜻으로 프로세스를 종료해도 된다.

 

 

예를들어 보자면

크기가 4인 배열이 다음과 있다고 하자

1회차: 가장 큰 수 10이 정렬된다.

정렬횟수 3회

 

2회차: 두번째 큰 수 6이 정렬된다.

정렬횟수 2회

 

3회차: 세번째 큰 수 4가 정렬된다.

정렬횟수 1회

 

시간 복잡도를 위해 정렬횟수를 모두 합하면 1부터 n-1까지의 합임을 알 수 있다.

따라서 시간 복잡도는 O(n^2)이다. ( n(n-1) / 2 )

 

 

 

 

II) 버블 정렬 구현

이론을 바탕으로 버블 정렬을 구현해보면 다음 코드와 같다.

n = int(input()) # 수의 개수
arr = []

for i in range(n):
    arr.append(int(input()))   # int로 형 변환 후 list에 넣어주자!!!!!!!!!!!!!!!!!!!!!

# 배열의 크기 만큼 반복
for i in range(len(arr)):
    # 배열의 크기에서 i 값과 1을 뺀 만큼 반복 
    for j in range(len(arr)-i-1):
        if arr[j] > arr[j+1]: # 앞에 있는 값이 더 크면 바꾼다.
            swap = arr[j]
            arr[j] = arr[j+1]
            arr[j+1] = swap
            
# 정답 출력하는 부분            
for i in range(len(arr)):
    print(arr[i])    
    
    

# sort 함수 이용한 풀이 
n = int(input()) # 수의 개수
arr = []

for i in range(n):
    arr.append(int(input()))   # int로 형 변환 후 list에 넣어주자!!!!!!!!!!!!!!!!!!!!!
arr.sort()
for i in range(len(arr)):
    print(arr[i])

위의 코드는 백준 2750번 문제와도 동일하다.

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

2750번: 수 정렬하기

 

직접 구현 할 수도 있고 파이썬의 내장 함수인 sort()나 sorted()를 통해서도 구할 수 있다.

sort(), sorted()에 자세한 설명이 궁금하다면 아래의 포스팅으로 ~~~

https://uoa6uoas.tistory.com/entry/파이썬-정렬-함수-sort-VS-sorted

[파이썬] 정렬 함수 (sort VS sorted)

 

 

 

 

 

<Summary>

- 버블 정렬  

 

*유의사항

- 알고리즘을 공부 중인 인공지능공학과 학부생이 공부하여 남긴 정리입니다.

- 정확하지 않거나, 틀린 점이 있다면 댓글로 알려주시면 감사하겠습니다.