알고리즘의 시작 정렬 알고리즘(sort Algorithm) 2. 버블 정렬

 

 

 

두번째 시간입니다.

 

오늘은 버블정렬 가지고 왔습니다.

 

 

버블정렬

---

버블정렬 또한 선택정렬과 같이 굉장히 직관적인 정렬 방법입니다.

바로

옆의 데이터와 비교해서 더 작은 값을 앞으로 보내자!

입니다.

 

[2,7,4,6,8,10,5,1,3,9]

자 전 시간과 같은 데이터가 있습니다.

 

맨 앞의 0,1 번째 데이터를 비교하면

 

[2,7,4,6,8,10,5,1,3,9]

 

변하질 않네요 다음 1,2번째 비교하면

 

[2,4,7,6,8,10,5,1,3,9]

[2,4,6,7,8,10,5,1,3,9]

[2,4,6,7,8,10,5,1,3,9]

[2,4,6,7,8,10,5,1,3,9]

[2,4,6,7,8,5,10,1,3,9]

.

.

.

이런식으로 변화하게 됩니다.

그럼 결국 첫번째 비교가 끝나면 가장 큰 값인

10이 오른쪽 끝으로 가겠죠? 그럼 그 큰 한번의

반복에서 가장 오른 쪽 값은 비교할 필요가 없는겁니다.

 

코드로 보시죠

 

data = [2,7,4,6,8,10,5,1,3,9]

for i in range(len(data)):
    for j in range(len(data)-1-i):
        if(data[j]>data[j+1]):
            temp = data[j]
            data[j] = data[j+1]
            data[j+1] = temp
print(data)

버블 정렬의 big O notation은

선택 정렬과 같은 O(N^2)

하지만 정렬중에 가장 비효율적이라고 할 수 있습니다.

 

오늘은 여기까지!