22년 11월 29일 TIL

정렬 : 데이터를 순서대로 나열하는 방법

컴퓨터에게 정렬을 시키기 위해서는 명확한 과정을 설명해줘야 한다.

 

두 변수의 값을 교체

다른 언어에서는 임시로 값을 저장해두는 변수를 따로 둬야 하지만

파이썬에선 a,b = b,a 라고 작성하면 된다.

>>> a = 3
>>> b = 4
>>> a, b = b, a
>>> print(a)
4
>>> print(b)
3

버블 정렬 

첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식

input = [4, 6, 2, 9, 1]


def bubble_sort(array):
    n = len(array) #배열의 길이

    for i in range(n):                    # 배열의 길이 만큼 반복 n=5, 0,1,2,3,4
        for j in range(n - i - 1):        # Q. 여기서 왜 n - i - 1 일까요? 
                                          # A. array[j] 와 array[j + 1] 을 비교할거라,
                                          #    마지막 원소까지 가지 않아도 되기 때문
            if array[j] > array[j + 1]:   # j번째 원소가 j+1번째 원소보다 크면
                array[j], array[j + 1] = array[j + 1], array[j] # 서로 교체(정렬함)
    return array


bubble_sort(input)
print(input)  # [1, 2, 4, 6, 9] 가 되어야 합니다!

시간 복잡도 : O(N^2) 만큼 걸린다.

 

선택 정렬

선택해서 정렬, 가장 작은 요소를 선택해서 가장 앞으로 데려온다(오름차순)

input = [4, 6, 2, 9, 1]


def selection_sort(array):
    n = len(array)
    for i in range(n - 1):       # n = 5, i = 0,1,2,3
        min_index = i            # 가장 작은 원소의 인덱스번호 저장
        for j in range(n - i):   # n = 5, i = 0,1,2,3 j = 5,4,3,2번 반복
            print(i, j, i + j)    
            if array[i + j] < array[min_index]: # array[i + j] 와 array[min_index] 비교
                min_index = i + j               # array[min_index]가 더 크다면 최소값 교체
        array[i], array[min_index] = array[min_index], array[i]
                                 # i번째 원소와 최소값 원소를 교체

    return array


selection_sort(input)
print(input)  # [1, 2, 4, 6, 9] 가 되어야 합니다!

시간 복잡도 : O(N^2) 만큼 걸린다.

삽입 정렬

전체에서 하나씩 올바른 위치에 "삽입" 하는 방식

선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만,

삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식입니다

input = [4, 6, 2, 9, 1]


def insertion_sort(array):
    n = len(array)
    for i in range(1, n):     # 1부터 4까지 i = 1,2,3,4
        for j in range(i):    # i만큼 j = 0  0,1  0,1,2  0,1,2,3 
        	if array[i - j - 1] > array[i - j]:  # i-j번째 요소보다 i-j-1번째 요소가 크면
                array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
            else:                                # 서로 교체
                break         #그렇지 않으면 더 볼 필요 없음					
    return array


insertion_sort(input)
print(input)  # [1, 2, 4, 6, 9] 가 되어야 합니다!

시간 복잡도 : O(N^2)   최선의 경우 : Ω(N)