Python Algorithm) 기본 정렬(bubble sort, selection sort, insertion sort)

1. bubble sort (버블정렬)

: 앞에서부터 swap해주면서 전체 길이의 n-1만큼 반복한다.

# 2020.08.18

# 버블정렬 O(n^2)
# 완전정렬이 되어있는 경우(최선의 경우) O(n)

def bubbleSort(data_list):
    for num in range(len(data_list)-1):
        swap = 0
        for idx in range(len(data_list)-num-1):
            if data_list[idx]>data_list[idx+1]:
                data_list[idx], data_list[idx+1] = data_list[idx+1], data_list[idx]
                swap += 1
        if swap == 0:
            break
    return data_list

data_list = [7,6,5,4,3,2,1]
print(bubbleSort(data_list))

2. selection sort (선택정렬)

: 기준값을 잡고 더 작은 숫자가 나오면 swap한다. 기준값을 한 칸씩 이동하면서 n-1번 반복한다.

# 선택정렬 O(n^2)
def selectionSort(data_list):
    for num in range(len(data_list)):
        lowest = num
        swap = 0
        for idx in range(num+1, len(data_list)):
            if data_list[lowest] > data_list[idx]:
                lowest = idx
                swap += 1
        data_list[num], data_list[lowest] = data_list[lowest], data_list[num]

        if swap == 0:
            break
    return data_list

data_list = [7,6,5,4,3,2,1]
print(selectionSort(data_list))

3. insertion sort (삽입정렬)

: 기준값을 한칸 씩 이동하면서 기준값의 앞에 있는 숫자들과 비교하여 기준값을 앞으로 이동시킨다.

# 삽입정렬 O(n^2)
def insertionSort(data_list):
    for num in range(1, len(data_list)):
        for idx in range(num, 0, -1):
            if data_list[idx-1] > data_list[idx]:
                data_list[idx], data_list[idx-1] = data_list[idx-1], data_list[idx]

    return data_list

data_list = [7,6,5,4,3,2,1]
print(insertionSort(data_list))

시간복잡도는 세 경우 모두 n개의 데이터를 n번씩 돌아야 하기 때문에 O(n^2)이다.