대학원 일기

힙 정렬 최대 힙 트리나 최소 힙트리를 구성해 정렬을 하는 방법 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 과정 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만든다. 그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다. 삭제되는 요소들(최대값부터 삭제)은 값이 감소되는 순서로 정렬되게 된다. 내림차순 힙정렬 과정 오름차순 힙정렬 과정 정렬 알고리즘 시간 복잡도 비교 Python Code def heap_sort(unsorted): n = len(unsorted) #최대 힙 만들기 #최소힙은 부등호만 반대로 바꿔주면 됨 for i in range(1, n): child = i while child != 0: ..

병합 정렬 비교 기반 정렬 알고리즘 병렬을 앞 부분과 뒷 부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘 안정한 정렬(Stable sort) 분할 정복 알고리즘 1945년 폰 노이만이 개발 과정 리스트의 길이가 0또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에 다음 과정을 거친다. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다. 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 합병 정렬은 다음의 단..

퀵 정렬 정렬 알고리즘 중 가장 빠른 알고라즘 중의 하나 찰스 앤터니 리처드 호어(C.A.R Hoare)가 명명 각 그룹에 피벗(pivot) 설정과 그룹 나눔을 반복하며 모든 그룹이 1명이 되면 정렬을 마침 피벗(pivot): 그룹을 나누는 기준을 말하며, 피벗은 마음대로 선택할 수 있고, 왼쪽 그룹과 온쪽 그룹 어디에 들어가도 상관없음 분할 정복 알고리즘이므로 재귀 호출을 사용하여 구현 분할 정복 알고리즘: 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 불안정 정렬에 속한다. 과정 리스트 안에 있는 한 요소를 선택한다. (요소 = pivot) 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의..

셸 정렬 단순 삽입 정렬의 장점을 살리고, 단점을 보완한 정렬 알고리즘 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법 셸 정렬은 개념을 이해하고 구현하기는 쉬우나 시간복잡도 분석은 조금 복잡하다. 장점 정렬을 맞쳤거나 정렬을 마친 상태에 가까워지면 정렬 속도가 매우 빨라진다. 단점 삽입할 위치가 멀리 떨어져 있으면 이동해야 하는 횟수가 많아진다. 셸 정렬 알고리즘의 예제 정렬 알고리즘 시간 복잡도 비교 Python Code def Shellsort(arr): h = 1 while h 0: for i in range(h,len(arr..

단순 선택 정렬 단순 선택 정렬은 가장 작은 요소부터 선택하여 알맞은 위치에 옮겨 정렬하는 알고리즘이다. 서로 떨어진 요소를 교환하기 때문에 안정적이지 않다. 시간 복잡도: $O(n^{2})$ Python Code def selectionSort(x): length = len(x) for i in range(length-1): indexMin = i for j in range(i+1, length): if x[indexMin] > x[j]: indexMin = j x[i], x[indexMin] = x[indexMin], x[i] return x Java Code void selectionSort(int[] list) { int indexMin, temp; for (int i = 0; i < list.l..

버블 정렬 버블 정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 $O(n^{2})$로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 양방향으로 번갈아 수행하면 칵테일 정렬이 된다. 정렬 알고리즘 중 가장 단순한 알고리즘이다. 정렬 알고리즘 시간 복잡도 비교 버블 정렬 장단점 장점 코드가 단순하여 구현하기 쉽다. (이해하기 쉬움) 적은 양의 데이터에서는 시간이 오래 걸리지 않아 적절하다. 단점 시간이 오래 걸린다. 비효율적인 방법이다. (성능이 좋지 않음) 실업무에서 사용하기 어렵다. (데이터가 많을 경우 시간이 오래 걸림) Python Code def bubbleSort(x): length = len(x)-1 for i in range(length): for j in ran..

알고리즘 알고리즘은 문제를 해결하기 위한 단계를 체계적으로 명시한 것을 의미한다. 문제를 해결하기 위한 것 명확하게 정의 순서가 있는 유한 개의 규칙으로 이루어진 작업 알고리즘의 조건 입력: 외부에서 제공되는 자료가 0개 이상 존재한다. 출력: 적어도 2개 이상의 서로 다른 결과를 내어야 한다. (모든 입력에서 하나의 출력만 나오면 안됨) 명확성: 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다. 유한성(종결성): 유한 개의 명령어를 수행한 후(유한 시간 내) 종료되어야 한다. 효율성: 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다. 알고리즘 연구 분야 고안: 완벽한 자동화를 통한 알고리즘의 개발은 불가능하므로 이미 증명된 유용한 알고리즘들을 습득함으로써 보다 유용한 알고리즘을..