버블정렬은 아이디어 자체는 매우 쉬운 알고리즘이다. 바로 옆에 있는 것과 비교해서 정렬하는 것이다. 아이디어가 쉬운 만큼 코드도 어렵지 않게 작성할 수 있지만, 효율성은 매우 낮다고 알려져 있어 앞으로 이런 코드를 쓸 일이 있을지는 잘 모르겠다. 그래도 알고리즘을 공부하는 입장에서 하나씩 접하면서 생각하는 습관이 필요할 것이다.

구현해보고자 하는 코드는 작은 값부터 큰 값까지 정렬하는 것으로, 우선 코드부터 살펴보면 다음과 같다.

# 옆에 있는 값과 비교해 더 작은 값을 앞으로 보내기
# 하지만, 효율성이 가장 낮은 알고리즘
def bubble_sort(array):
    for i in range(len(array)):
        for j in range(len(array)-i-1):
            if (array[j] > array[j+1]):
                temp = array[j]
                array[j] =array[j+1]
                array[j+1] = temp
            print(array)
array = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]
bubble_sort(array)

선택정렬을 위한 알고리즘의 순서는 다음과 같다. 사실은 더 간단하게 나타낼 수도 있지만, 설명을 위해 비교적 길게 풀어쓴다.

1. 이전 비교 리스트에서 비교할 집단을 하나 줄여 선택한다. (첫번째 ~ 마지막 하나 전) 

2. 비교할 집단 내에서 원소를 순차적으로 선택한다

3. 선택한 원소가 옆의 원소와 비교해 앞의 값이 큰 경우, 데이터를 교환한다

3. 2~3를 반복하다가, 비교 집단의 원소를 모두 선택한 경우 1로 돌아간다

여기서 헛갈릴 수 있는 부분이 몇 가지가 보이는데, 우선 첫번째부터 마지막까지 원소가 가는 것이 아닌 마지막 하나 전까지만 가야한다는 점이다. 왜냐하면, 내가 선택한 원소(j)와 그 바로 다음 원소(j+1)를 비교할 것이기 때문이다.

다른 하나는 비교해야할 집단을 하나씩 줄여준다는 점이다. 이는 비교집단의 모든 원소를 비교하면, 집단의 맨 마지막에 가장 큰 원소가 위치하게 된다. (이는 직접 해보는 것만큼 이해가 빠른 것은 없는 듯하다) 생각해보면 앞서 위에서 얘기한 것과 비슷한 원리라고 느껴지기도 하는데, 이건 사람마다 다르게 생각할 수 있어 따로 설명은 하지 않으려고 한다.

아무튼, 위 코드를 구현해보면 아래와 같이 잘 정렬하는 것을 볼 수 있다.

출처 및 참고:

- 안경잡이개발자, "3. 버블 정렬(Bubble Sort)", https://blog.naver.com/ndb796/221226803544

정렬 알고리즘 중 하나인 선택정렬(selection sort)은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 알고리즘이다. 알고리즘에 대한 공부를 위해 적절한 강의를 찾았는데, 기본적으로 제공되는 내용은 C를 기반으로 하기 때문에 이를 Python으로 바꿔서 해보려고 한다.

(모든 내용은 아래 참고의 블로그 및 유튜브를 참조)

선택정렬을 하기 위해서 실행하는 알고리즘의 순서는 다음과 같다.

1. 주어진 배열을 하나씩 탐색한다.

2. 탐색 지점부터 배열의 끝까지 값 중 가장 작은 값을 찾는다.

3. 그 작은 값을 탐색 지점에 놓고, 탐색 지점의 값을 가장 작은 값이 있던 곳에 놓는다. (데이터 교환, 스와핑)

그 전체 알고리즘은 아래와 같다.

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

# 가장 작은 것을 선택해 제일 앞으로 보내기
def selection_sort(array):
    for i in range(len(array)):
        bound = 9999  # 비교를 위해서 데이터의 어떤 값보다 큰 숫자
        # 가장 작은 것을 찾고, 그 위치를 ind에 저장
        for j in range(i, len(array)):
            if (bound > array[j]):
                bound = array[j]
                ind = j
        # 스와핑 
        temp = array[i]
        array[i] = array[ind]
        array[ind] = temp
    print(array)

selection_sort(array)

결과는 잘 나오는 것으로 볼 수 있다. 다만, 이 알고리즘이 어떻게 동작하는지 보려면 함수 맨 마지막에 있는 print 함수를 들여쓰기해서 아래 코드 처럼 쓰면, 어떻게 동작하는지 잘 볼 수 있을 것이다. 

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

# 가장 작은 것을 선택해 제일 앞으로 보내기
def selection_sort(array):
    for i in range(len(array)):
        bound = 9999  # 비교를 위해서 데이터의 어떤 값보다 큰 숫자
        # 가장 작은 것을 찾고, 그 위치를 ind에 저장
        for j in range(i, len(array)):
            if (bound > array[j]):
                bound = array[j]
                ind = j
        # 스와핑 
        temp = array[i]
        array[i] = array[ind]
        array[ind] = temp
    	print(array)

selection_sort(array)

참고:

- 안경잡이개발자, "2. 정렬의 개요와 선택정렬(Selection Sort)", https://blog.naver.com/ndb796/221226800661

Python을 하다보면, 2d-array가 필요한 경우가 종종 생긴다. 바로 직전에 올렸던 scipy linprog 이용할 때도 2d array가 필요했던 것처럼 말이다. 물론, 개수가 얼마 안된다면, 코드를 생각하면서 만드는 것보다는 하나씩 입력하는 게 빠를 테지만, 사람의 손으로 할 수 없는 범위까지 가게 된다면 코드를 작성하는 것이 훨씬 편리하다. 코드를 결론부터 얘기하자면, 아래와 같다.

value = [1,2,3,4,5]		#입력 값
data_list = []

for line in range(3):
    data_list.append([])		# A
    for item in value:			
        data_list[-1].append(item)	# B
        
print(data_list)

value를 입력받아서, data_list에 2d_array로 만드는 과정이다. 사실 여기서는 입력값이 value로 한정되어 있어서, [1,2,3,4,5]만 반복되는 형태이지만, 만일 조금더 동적으로 다양한 데이터가 있다면 조금 응용해서 동적으로 입력하는 코드도 작성이 가능하다.

각 라인별로 해석은 아래와 같다.

A: data_list에 []를 range(3), 즉 3번 반복해서 추가해준다.  여기서 명심해야 할 것은 value가 리스트형이므로, 2d-array를 형성하기 위해서는 append를 사용해야 한다는 점이다.

B: value안에 있는 값들을 하나씩(item) 넣어주게 되는데, A에서 첫번째 data_list의 형태는  [ [] ]에 안쪽 리스트에 item을 넣어준다. 두번째는 [ [1,2,3,4,5], [] ]가 될 것이고 거기 index = -1에 item을 넣어주므로 [ [1,2,3,4,5], [1,2,3,4,5]]가 될 것이다. 마지막 세번째도 똑같이 적용하면 아래와 같은 결과 값을 얻게 된다.

Out : [[1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5]]

만일에 index -1을 설정안해준 코드를 적용해보면 어떨까? 그런 경우를 상정해서 아래와 같이 변경했다.

value = [1,2,3,4,5]	
data_list = []

for line in range(3):
    data_list.append([])		
    for item in value:			
        data_list.append(item)	# 여기만 [-1] 빼서 수정
        
print(data_list)

이럴 경우, 첫번째 만들어진  [ [] ] 에 item들을 넣어주는 것이기 때문에 1번 루프를 돌고나면, [ [], 1,2,3,4,5]가 만들어진다. 똑같은 논리로 이후 루프도 돌기 때문에 아래와 같은 결과가 나오게 되므로 주의해야 한다.

Out : [[], 1, 2, 3, 4, 5, [], 1, 2, 3, 4, 5, [], 1, 2, 3, 4, 5]