[알고리즘] 시간 복잡도 o(n^2) 정렬: selection sort, insertion sort, bubble sort

부제: 백준 2750번 수 정렬하기

벌써 자료 구조를 배운지 4년이라는 시간이 지났다🤭
가물 가물 해가는 기억을 되살리기 위해 백준 문제를 다시 풀어보기 시작했는데,
정리의 필요성을 깨닫고 velog에 글을 써야겠다고 생각했다.

백준 2750번 문제는 시간 복잡도 o(n^2)를 가지는 정렬 알고리즘으로 주어진 숫자들을 정렬하는 문제이다.

먼저 o(n^2)를 가지는 정렬 알고리즘으로는 1. 선택 정렬 (selection sort) 2. 삽입 정렬 (insertion sort) 3. 버블 정렬 (bubble sort) 등이 있다.
문제는 이 3가지 정렬 중 하나를 구현하면 맞출 수 있지만 기왕 하는거 3개 다 함수로 구현 해보고자 했다.

📌선택 정렬(selection sort)

선택 정렬은 정렬되지 않은 배열에서 가장 작은 수를 찾아 (선택해서) 가장 앞의 인덱스와 교환하는 알고리즘이다.

1. 첫번째 인덱스부터 차례로 값을 하나씩 선택한다.
2. 내가 선택한 인덱스 다음 인덱스부터 배열에 있는 가장 작은 값을 찾는다.
3. 가장 작은 값과 내가 선택한 인덱스의 값을 교환한다.

# selection sort
def select_sort(array):
    for i in range(len(array)):
        for j in range(i+1, len(array)):
            if array[i] > array[j]:
                tmp = array[i]
                array[i] = array[j]
                array[j] = tmp
    return array

📌삽입 정렬(insertion sort)

삽입 정렬은 배열이 정렬 된 부분과 배열 안된 부분으로 나누었을 때, 배열 된 부분에 배열 안된 부분의 값들을 하나씩 추가(삽입)해서 정렬하는 알고리즘이다.

1. 배열의 두번째 인덱스 값을 선택한다. (처음에만)
2. 선택한 인덱스 앞에 있는 값들과 비교하며 정렬한다.
3. 선택한 인덱스 다음의 인덱스 값을 선택하여 1-2번을 반복한다.

# insertion sort
def insert_sort(array):
    for i in range(1, len(array)):
        for j in range(i, 0, -1):
            if array[j-1] > array[j]:
                tmp = array[j-1]
                array[j-1] = array[j]
                array[j] = tmp 
    return array

📌버블 정렬(bubble sort)

인접한 두 인덱스의 값들을 비교하며 교환하는 정렬 알고리즘이다.

1. 배열 첫 부분부터 인접한 인덱스들을 두개씩 선택한다.
2. 작은 값이 앞에 오도록 값들을 교환해 나간다.

# bubble sort
def bubble_sort(array):
    for i in range(len(array)):
        for j in range(i, len(array)):
            if array[i] > array[j]:
                tmp = array[i]
                array[i] = array[j]
                array[j] = tmp
    return array

전체 코드

import sys

# selection sort
def select_sort(array):
    for i in range(len(array)):
        for j in range(i+1, len(array)):
            if array[i] > array[j]:
                tmp = array[i]
                array[i] = array[j]
                array[j] = tmp
    return array

# insertion sort
def insert_sort(array):
    for i in range(1, len(array)):
        for j in range(i, 0, -1):
            if array[j-1] > array[j]:
                tmp = array[j-1]
                array[j-1] = array[j]
                array[j] = tmp 
    return array

# bubble sort
def bubble_sort(array):
    for i in range(len(array)):
        for j in range(i, len(array)):
            if array[i] > array[j]:
                tmp = array[i]
                array[i] = array[j]
                array[j] = tmp
    return array

N = int(sys.stdin.readline().strip())
array = []

for i in range(N):
    n = int(sys.stdin.readline().strip())
    array.append(n)

array = bubble_sort(array)
for i in range(len(array)):
    print(array[i])

간단한 알고리즘이고 이미 잘 정리된 포스팅들이 많지만
그래도 내가 써보고 싶어서 기록해둔다 ㅋㅋㅋ
끄읕✨