정렬 - 버블정렬

[정렬이란?]

데이터를 순서대로 나열하는 방법을 의미

정렬은 알고리즘의 굉장히 중요한 주제임

데이터를 조금 더 효율적으로 탐색할 수 있게 만들기 때문

 

컴퓨터에 정렬을 시키기 위해서는 명확한 과정을 설명해줘야함

 

 

[버블정렬]

첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를,

...

(마지막 - 1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식

작은 숫자, 큰 숫자 순서로 있으면 냅두고

큰 숫자, 작은 숫자 순서로 있으면 둘의 위치를 변경

버블 정렬

---

[문제]

다음과 같이 숫자로 이루어진 배열이 있을 때, 오름차순으로 버블 정렬을 이용해서 정렬하시오.

 

 

 

풀이)

input = [4, 6, 2, 9, 1]


def bubble_sort(array):                   #O(N^2)
    for i in range(len(array)-1):         # N의 길이만큼 반복
        for j in range(len(array)-1-i):   # N의 길이만큼 반복
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return array


bubble_sort(input)
print(input)  # [1, 2, 4, 6, 9]

 

 

 

맨 오른쪽을 보면 옆과 비교하면서 최댓값이 찾아지면서 쌓아지는구나 라고 생각하면 됨