컴알 시험대비

삽입, 삭제, 선택정렬은 실습

쉘, 퀵, 힙 정렬은 코드

 

선택정렬 - 2중 for문 인덱스 기억해서 마지막에 스왑
삽입정렬 - 1번부터 시작하는 i for문, j = i-1로 지정하고 while루프를 j가 0보다 작아지거나 j값이 key값 보다 클때까지 돌면서 값을 한칸씩 뒤로 민다, 마지막에
arr[j+1] = key
버블정렬 i for문은 i 길이만큼 j for문은 len(arr)-i-1로 n-1부터 한칸씩 줄여가면서 돈다, 최적화를 위해 arr[j]와 arr[j+1]이 바뀌지 않으면 바로 종료한다
 

선택정렬 항상 n**2

삽입정렬 - 역순정렬시 최악

버블정렬  - 역순정렬시 최악

 

쉘정렬

홀수 gap, j = i하고 반복문 돌면서 j -= gap, 반복문을 다 돌면 gap // 2 해주기

def shell_sort(a) :
    n = len(a)
    gap = n // 2
    while gap >= 1:
        if (gap % 2) == 0: gap += 1
        for i in range(gap, n):
            j = i
            while j >= gap and a[j] < a[j-gap]: #삽입 위치를 찾음
                a[j], a[j-gap] = a[j-gap], a[j] #항목 이동
                #print('j = ',j,' gap = ', gap)
                j -= gap
        print(' Gap=', gap, a)
        gap = gap // 2

a = list(map(int, input().split()))
print("Original :", a)
shell_sort(a)
print("Shell :", a)

힙정렬, 아마 0번부터 시작하는 배열이 나올 것 같다

def heapify(arr, heap_size, index):
    largest = index
    left = 2 * index + 1  # 왼쪽 자식 노드의 인덱스
    right = 2 * index + 2  # 오른쪽 자식 노드의 인덱스

    if left < heap_size and arr[left] > arr[largest]:
        largest = left
    if right < heap_size and arr[right] > arr[largest]:
        largest = right

    if largest != index:
        arr[index], arr[largest] = arr[largest], arr[index]
        heapify(arr, heap_size, largest)


def heap_sort(arr):
    n = len(arr)
    
    # 처음에 최대 힙을 만들어줍니다.
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 맨 앞의 값을 맨 뒤로 보내고 힙을 재구성합니다.
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

arr = list(map(int, input().split()))
heap_sort(arr)
print("힙 정렬 결과:", arr)

1번부터 시작하는 배열

def heapify(arr, heap_size, index):
    largest = index
    left = 2 * index
    right = 2 * index + 1
    if left <= heap_size and arr[left] > arr[largest]:
        largest = left
    if right <= heap_size and arr[right] > arr[largest]:
        largest = right

    #부모와 자식간에 교환이 일어남
    if largest != index :
        arr[index], arr[largest] = arr[largest], arr[index]
        heapify(arr, heap_size, largest)


def heap_sort(arr):
    n = len(arr)
    #처음에 최소 힙 만들어주기
    for i in range (n//2, 0, -1):
        heapify(arr, n-1, i)

    #맨 앞의 값을 맨 뒤로 보내고 인덱스를 하나 줄여서 다시 힙히파이
    for i in range (n-1, 0, -1):
        arr[1], arr[i] = arr[i], arr[1]
        heapify(arr, i-1, 1)


arr = list(map(int, input().split()))
arr = [0] + arr
print(arr[1:])

heap_sort(arr)
print("힙 정렬 결과:", arr[1:])