버블정렬[bubble sort]

버블정렬이란
인접한 두개의 원소를 비교하며 자리를 계속 교환하는 방식이다.

시간복잡도: O(n**2)

---

정렬과정

 

1.  첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동
2. 한 단계가 끝나면 가장 큰 원소가 마지막에 배열

python으로 코드를 가볍게 표현하자면

#버블정렬
arr = [0,3,2,5,6,7,9,8,1]
for i in range(len(arr) - 1, 0, -1):
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
print(*arr)

외부 반복문에서는 뒤에서 부터 범위를 줄여가고, 내부반복문을 통해 0번 index부터 외부반복문의 변수인 i까지 크기를 비교하며 큰 숫자를 arr이란 배열의 오른쪽 가장자리로 보내는 알고리즘이다. 내부반복문이 끝날시 가장큰 숫자는 계속해서 i-1번의 index로 이동하게 되고 외부for문이 끝날시 arr은 올림차순으로 변한걸 볼 수 있다.

그럼 결과적으로 output은

0 1 2 3 5 6 7 8 9

이 나오게된다.