[Python] 정렬 / 버블 정렬(Bubble sort) / 선택 정렬(Selection sort)

버블 정렬

버블 정렬이란, 인접한 두 항목을 비교해서 정렬하는 방식입니다.
항목이 거품처럼 올라오는 듯해서 버블 정렬이라고 합니다.

버블 정렬

def bubbleSort(seq):
    length = len(seq)
    for i in range(length - 1):            # 0부터 length - 1 까지
        for j in range(length - i - 1):    # j번째와 j+1번째 요소와 비교해서 스왑합니다.
            if seq[j] > seq[j + 1]:
                seq[j], seq[j + 1] = seq[j + 1], seq[j]
        print("{}번째 : {}".format((i+1), seq))    # 단계별로 출력해보기

    return seq

처음부터 탐색하며 현재 원소가 다음 원소보다 크면 서로 위치를 바꾸고, 그렇지 않다면 다음 원소로 탐색을 이동합니다.
그렇게 되면 1단계가 끝나게 된 후에 리스트 내의 가장 큰 값이 리스트의 마지막에 위치하게 되고
다음 단계부터는 뒤에서 두번째 원소까지 탐색을 이어갑니다.

 

• 1단계 수행 절차
  

  

정렬 전 리스트가 [4, 5, 2, 1, 6, 2, 7, 10, 13, 8] 라고 한다면, 각 단계별로 출력되는 결과입니다.

1번째 : [4, 2, 1, 5, 2, 6, 7, 10, 8, 13]
2번째 : [2, 1, 4, 2, 5, 6, 7, 8, 10, 13]
3번째 : [1, 2, 2, 4, 5, 6, 7, 8, 10, 13]
4번째 : [1, 2, 2, 4, 5, 6, 7, 8, 10, 13]
5번째 : [1, 2, 2, 4, 5, 6, 7, 8, 10, 13]
6번째 : [1, 2, 2, 4, 5, 6, 7, 8, 10, 13]
7번째 : [1, 2, 2, 4, 5, 6, 7, 8, 10, 13]
8번째 : [1, 2, 2, 4, 5, 6, 7, 8, 10, 13]
9번째 : [1, 2, 2, 4, 5, 6, 7, 8, 10, 13]
정렬 끝

 

선택 정렬

선택 정렬이란, 리스트의 해당 순서에 어떤 원소를 넣을지 선택하며 정렬하는 방식입니다.
내림차순으로 정렬한다면, 첫번째 원소에는 가장 작은값을 찾아 넣어줄거기 때문에
리스트에서 가장 작은값을 찾아 첫번째 원소와 위치를 바꿉니다.
두번째는 남은 원소들중 가장 작은 값을 찾아 두번째 원소와 위치를 바꿉니다.
반복하여 내림차순으로 정렬을 완료합니다.

선택 정렬

def selection_sort(seq):
    length = len(seq)

    for i in range(length - 1):
        min_i = i
        for j in range(i + 1, length):
            if seq[min_i] > seq[j]:
                min_i = j
        seq[i], seq[min_i] = seq[min_i], seq[i]

    return seq

• 단계별 수행 절차
  

  

정렬 전 리스트가 [11, 3, 28, 43, 9, 4] 라고 한다면,
각 단계별로 출력되는 결과입니다.

1번째 : [3, 11, 28, 43, 9, 4]
2번째 : [3, 4, 28, 43, 9, 11]
3번째 : [3, 4, 9, 43, 28, 11]
4번째 : [3, 4, 9, 11, 28, 43]
5번째 : [3, 4, 9, 11, 28, 43]
정렬 끝