항해99 TIL 2주차 - 12

정렬

정렬이란 데이터를 크기 순으로 나열 하는 것을 말한다.
정렬에는 큰 값 부터 나열하는 내림차순이 있고, 작은 값 부터 나열하는 내림차순이 있으며 오늘 학습한 정렬으로는 버블정렬, 선택정렬, 삽입정렬이 있다

버블정렬

버블정렬이란 서로 인접한 두 원소를 비교해가며 정렬하는 알고리즘

1. 1번째 원소와 2번째와 비교한 후 크다면 교체, 아니라면 유지
2. 2번째 원소와 3번째 원소를 비교한 후 크다면 교체, 아니라면 유지
3. 6번째 원소까지 도달 했다면 1번째 원소부터 다시 2번째 원소와 비교
4. 이렇게 오름차순으로 정렬이 될때까지 무한반복

버블정렬 구현 코드

def bubblesort(lst):
    # 최댓값을 구하는 알고리즘을 len(lst) - 1 만큼 반복한다.
    iters = len(lst) - 1
    for iter in range(iters):
        # 이미 구한 최댓값은 범위에서 제외한다.
        wall = iters - iter
        for cur in range(wall):
            if lst[cur] > lst[cur + 1]:
                lst[cur], lst[cur + 1] = lst[cur + 1], lst[cur]
    return lst

선택정렬

선택정렬이란 나열되어있는 값 중 가장 작은 값을 찾은 후 1번 인덱스와 교체하고 1번 인덱스를 제외하고 가장 작은 값을 찾아서 2번 인덱스와 교체하는 방식으로 1번부터 5번 인덱스까지 오름차순으로 데이터가 정렬되는 알고리즘

선택정렬 구현 코드

def selectionsort(lst):
    iters = len(lst) - 1
    for iter in range(iters):
        minimun = iter
        for cur in range(iter + 1, len(lst)):
            if lst[cur] < lst[minimun]:
                minimun = cur

        if minimun != iter:
            lst[minimun], lst[iter] = lst[iter], lst[minimun]

    return lst

삽입정렬

삽입정렬이란 2번째 인덱스에 있는 값부터 시작해서 왼쪽에 있는 값들과 비교한 후 자료를 뒤로 옮기고 2번째 인덱스에 값을 지정된 자리로 옮기는 알고리즘

1. 2번 인덱스의 왼쪽 인덱스와 비교해서 2번 인덱스의 값이 더 작다면 자료를 뒤로 옮기고 2번 인덱스의 값을 지정된 자리로 옮긴다
2. 3번째 인덱스와 왼쪽에 있는 인덱스와 비교한 후 3번 인덱스가 더 작다면 위와 같이 실행하고 더 크다면 그대로 둔다.
3. 위에서와 같은 동작을 1번부터 마지막 인덱스까지 오름차순으로 나열될때까지 한다.

def insertionsort(lst):
    # 0번째 요소는 이미 정렬되어있으니, 1번째 ~ lst(len)-1 번째를 정렬하면 된다.
    for cur in range(1, len(lst)):
        # 비교지점이 cur-1 ~ 0(=cur-cur)까지 내려간다.
        for delta in range(1, cur + 1):
            cmp = cur - delta
            if lst[cmp] > lst[cmp + 1]:
                lst[cmp], lst[cmp + 1] = lst[cmp + 1], lst[cmp]
            else:
                break
    return lst


def insertionsort_2(lst):
    for idx in range(1, len(lst)):
        val = lst[idx]
        cmp = idx - 1

        while lst[cmp] > val and cmp >= 0:
            lst[cmp + 1] = lst[cmp]
            cmp -= 1

        lst[cmp + 1] = val

    return lst