[알고리즘] 버블 정렬

0. 알고리즘 연습방법

- 알고리즘을 잘 작성하기 위해서는 잘 작성된 알고리즘을 이해하고 스스로 만들어봐야 함

  - 모사! 그림을 잘 그리기 위해서는 잘 그린 그림을 모방하는 것부터 시작

 

<알고리즘 연습 방법>

- 연습장과 펜을 준비한다.

- 알고리즘 문제를 읽고 분석한다.

- 간단하게 테스트용으로 매우 간단한 경우부터 복잡한 경우 순서대로 생각해보면서, 연습장과 펜을 이용하여 알고리즘을 생각해본다.

- 가능한 알고리즘이 보인다면, 구현할 알고리즘을 세부 항목으로 나누고, 문장으로 세부 항목을 나누어서 적어본다.

- 코드화하기 위해, 데이터 구조 또는 사용할 변수를 정리한다.

- 각 문장을 코드 레벨로 적는다.

- 데이터 구조 또는 사용할 변수가 코드에 따라 어떻게 변하는지 손으로 적으면서 임의 데이터로 코드가 정상작동하는지를 연습장과 펜으로 검증한다.

 

1. 정렬 알고리즘이란

- 정렬 : 어떤 데이터들이 주어 졌을 때 이를 정해진 순서대로 나열하는 것

- 정렬은 프로그램 작성시 빈번하게 필요로 함

- 다양한 알고리즘이 고안되었으며, 알고리즘 학습의 필수

 

다양한 정렬 알고리즘 이해를 통해, 동일한 문제에 대해 다양한 알고리즘이 고안될 수 있음을 이해하고,

각 알고리즘간 성능 비교를 통해, 알고리즘 성능 분석에 대해서도 이해할 수 있음

 

2. 버블 정렬이란

- 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘

직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

 

3. 어떻게 코드로 만들까 

데이터가 4개 일때(데이터 갯수에 따라 복잡도가 떨어지는것은 아님, 4개로 로직을 이해해보자)

예: data_list = [1,9,3,2]

- 1차 로직 적용

1와 9비교, 자리바꿈없음 [1,9,3,2]

9와 3비교, 자리바꿈 [1,3,9,2]

9와 2비교, 자리바꿈 [1,3,2,9]

 

- 2차 로직 적용

1와 3 비교, 자리바꿈없음[1,3,2,9]

3과 2 비교, 자리바꿈 [1,2,3,9]

3화 9 비교, 자리바꿈없음 [1,2,3,9]

 

-3차 로직 적용

1과 2 비교, 자리바꿈없음 [1,2,3,9]

2과 3 비교, 자리바꿈없음 [1,2,3,9]

3과 9 비교, 자리바꿈없음 [1,2,3,9]

 

4. 알고리즘 구현

특이점 찾아보기

- N개의 리스트가 있는 경우 최대 N-1번의 로직을 적용한다.

- 로직을 1번 적용할 때마다 가장 큰 숫자가 뒤에서부터 1개씩 결정된다.

- 로직이 경우에 따라 일찍 끝날 수도 있다. 따라서 로직을 적용할 떄 한번도 데이터가 교환된 적이 없다면 

이미 정렬된 상태이므로 더 이상 로직을 반복 적용할 필요가 없다.

 

1. for num in range(len(data_list)) 반복

2. swap = 0 (교환이 되었는지를 확인하는 변수를 둠)

3. 반복문 안에서, for index in range(len(data_list)-num-1) n-1번 반복해야 함

4. 반복문안의 반복문 안에서, if(data_list[index] > data_list[index +1] 이면

5. data_list[index], data_list[index + 1] = data_list[index + 1], data_list[index], swap += 1

6. 반복문 안에서, if swap == 0 이면 break 끝

 

5. 버블 정렬 코드 및 확인

# 버블 정렬 함수
def buble_sort(data_list):
    for index in range(len(data_list)-1):
        swap = False
        for index2 in range(len(data_list)-index-1):
            if data_list[index2] > data_list[index2+1] :
                data_list[index2], data_list[index2+1] = data_list[index2+1], data_list[index2]
                swap = True
        if swap == False :
            break
    return data_list
    
    
# 버블 정렬 함수 확인
import random
data_list = random.sample(range(100), 10)
print(data_list)
print (buble_sort(data_list))

 

6. 알고리즘 분석

- 반복문이 두개 O(n^2) 최악의 경우 n*(n-1) /2

- 완전 정렬이 되어 있는 상태라면 최선은 O(n)