본문 바로가기

전체 글133

알고리즘 - 셸 정렬 단순 삽입 정렬의 장점은 살리고 단점을 보완해, 더 빠르게 정렬하는 알고리즘을 셸 정렬이라고 합니다. 셸 정렬은 먼저 정렬할 배열의 원소를 그룹으로 나누어, 각 그룹별로 정렬을 수행합니다. 그리고 정렬된 그룹을 합치는 작업을 반복하여 원소의 이동 횟수를 줄이는 방법입니다. 위와 같이 8개의 원소를 갖는 배열이 있을 때, 단순 삽입 정렬은 1을 맨 앞으로 이동시킬 때 총 7번 이동시켜야 합니다. 셸 정렬을 하면 먼저 서로 4칸씩 떨어진 원소를 꺼내어 4개의 그룹으로 나누고 그룹별로 각각 정렬합니다. (8, 5), (4, 2), (9, 7), (6, 1) --> (5, 8), (2, 4), (7,9), (1, 6) 이렇게 4칸 떨어진 원소를 정렬하는 방법을 4-정렬이라고 합니다. 이어서 2칸 떨어진 원소를 .. 2020. 11. 24.
알고리즘 - 이진 삽입 정렬 단순 삽입 정렬은 배열 원소 수가 많이지면 비교, 교환 비용이 커지는데 이진 삽입 정렬을 사용하면 정렬을 마친 배열을 제외하고 원소를 삽입해야 할 위치를 검사해서 비용을 줄일 수 있습니다. def binary_insertion_sort(a): n = len(a) for i in range(1, n): key = a[i] pl = 0 pr = i - 1 while True: pc = (pl + pr) // 2 if a[pc] == key: break elif a[pc] pr: break if pl > a[0] = 4 이렇게 교환이 됩니다. 이렇게 검색 범위를 축소하고 가운데 값을 기준으로 검색 범위를 좁혀 나가는 것이 이진 삽.. 2020. 11. 23.
알고리즘 - 단순 삽입 정렬 4 2 1 7 9 6 오름차순으로 정렬을 할 때, 위 배열에서 현재 원소 2를 보고있다면 2는 4보다 앞에 있어야 하기 때문에 2 4 1 7 9 6 이렇게 앞으로 한 칸 옮겨주면 됩니다. 원소 1을 올기면 4와 2를 지나쳐 맨 앞으로 옮겨줍니다. 1 2 4 7 9 6 이렇게 가장 작은 원소를 정하는 것이 아닌, 현재 보고 있는 원소를 알맞은 위치로 옮기는 것을 단순 삽입 정렬이라고 합니다. def insertion_sort(a) -> None: n = len(a) for i in range(1, n): j = i tmp = a[i] while j > 0 and a[j - 1] > tmp: a[j] = a[j-1] j -= 1 a[j] = tmp print('단순 삽입 정렬') num = int(input.. 2020. 11. 23.
알고리즘 - 버블 정렬 버블 정렬은 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘입니다. 4 1 9 2 5 7 3 위와 같은 배열이 있을 때, 오름차순으로 배열을 정렬한다고 생각해봅시다. 이렇게 두 수를 비교하면서 작은 수면 자리를 교환 하고 계속 비교해 나갑니다. 계속 비교하면 가장 작은 수인 1이 제일 앞으로 오게 되고 다음으로 작은 수들이 오도록 비교, 교환 해줘야하고, 이 배열의 크기가 7이기 때문에 이러한 비교, 교환을 총 7 - 1 = 6번 해줘야 오름차순으로 정렬됩니다. 이제 코드로 살펴보겠습니다. def bubble_sort(a) -> None: n = len(a) for i in range(n - 1): for j in range(n - 1, i, -1): if a[j-1] > a.. 2020. 11. 20.

티스토리툴바