SY DevLog

힙 정렬(Heap Sort) 힙(heap)을 이용하는 정렬 알고리즘 힙(heap) : 부모 노드의 값이 자식 노드의 값보다 큰 완전이진트리 부모 노드의 값이 자식 노드의 값보다 항상 크기 때문에 힙의 루트에는 제일 큰 수가 들어가게 된다. 이를 이용하여 힙의 루트 값을 꺼내어 배열의 오른쪽부터 채워넣으면서(오름차순 기준) 배열을 정렬할 수 있다. 힙으로 만들기 -> 배열의 맨 오른쪽부터 루트값 채워넣기 -> 다시 힙으로 만들기 -> 루트값 채워넣기 ... 이렇게 배열의 정렬이 완료될 때까지 힙 만들기와 루트값 넣기를 반복하여 정렬을 한다. 시간 복잡도 : O(NlogN) 힙으로 만들 때 걸리는 시간 복잡도는 O(NlogN), 힙에서 루트값을 꺼내는데 걸리는 시간 복잡도는 O(1) 이므로 힙 정렬의 시간 ..

병합 정렬(Merge Sort) 배열을 두 개로 쪼개어서 정렬을 한 뒤, 다시 병합하는 작업을 반복하는 정렬 알고리즘 배열을 중앙을 기준으로 앞(left ~ center)과 뒤(center+1 ~ right)로 나눈다. 이 작업을 배열의 요소가 2개가 될 때까지 반복한다. 나누어진 두 개의 배열을 정렬한 뒤 하나의 배열로 병합한다. 이렇게 배열을 모두 정렬 및 병합하면 종료한다. 시간복잡도 : O(NlogN) 퀵 정렬은 최악의 경우 시작복잡도가 O(N²) 이지만, 병합 정렬은 O(NlogN)로 유지된다. [예제] 배열 arr의 요소가 5 9 3 1 8 6 4 7 2 일 때, 이 배열을 오름차순으로 정렬하기 먼저 배열 arr의 left = 0, right = arr.length -1 로 초기화해준다. le..

퀵 정렬(Quick Sort) 알고리즘이 매우 빠르다라고 해서 붙여진 이름이다. 기준이 되는 피벗(pivot)을 설정하고, 그룹을 반복적으로 나누어서 정렬을 하는 알고리즘이다. 퀵 정렬은 피벗을 배열의 왼쪽 끝으로 설정하냐, 오른쪽 끝으로 설정하냐, 가운데로 설정하냐에 따라서 속도가 달라진다. 퀵 정렬의 알고리즘을 간단히 설명하면 이렇다. 배열의 왼쪽 끝 요소를 가리키는 커서를 pl, 오른쪽 끝 요소를 가리키는 커서를 pr 로 한다. 그리고 피벗을 가운데 값인 8로 한다고 하자. 피벗을 기준으로 왼쪽에 있는 구역을 A 구역, 오른쪽에 있는 구역을 B 구역이라고 할 때, A 구역에서는 pl을 오른쪽으로 이동시키면서 8보다 큰 값들을 찾아서 B 구역으로 넘기고, B 구역에서는 pr을 왼쪽으로 이동시키면서 8..

단순 삽입 정렬(Straight Insertion Sort) 선택한 요소를 그보다 앞쪽의 나열된 요소들 중, 알맞은 위치에 '삽입하는' 알고리즘 선택한 요소의 앞부분은 정렬이 완료된 상태이다. 삽입된 위치 이후의 요소들은 한칸씩 뒤로 밀려나게 된다. 알고리즘 : 배열의 두번째 요소부터 시작하여 하나씩 요소를 선택한다. 선택된 요소(arr[n])를 tmp 변수에 임시저장한다. * 변수 tmp에 임시저장하는 이유 : 왼쪽의 요소들을 한칸씩 오른쪽으로 미는 과정에서 선택된 요소(arr[n])가 있던 n번째 자리가 다른 값으로 채워지게 된다. 그렇게 되면 뒤에가서 arr[n]의 원래있던 값이 필요할 때 가져올 수 없으므로 tmp에 저장해둔다. 선택된 요소(tmp)보다 앞쪽에 있는 요소들(arr[0] ~ arr[..

단순 선택 정렬(Straight Selection Sort) 가장 작은 요소를 골라서 배열의 왼쪽부터 차례대로(오름차순 기준) 알맞은 위치로 옮겨서 정렬하는 방법 알고리즘 : 첫 번째 요소부터 차례대로 비교 기준(arr[n])이 된다.비교 기준의 다음번째 위치부터 마지막까지, 각각의 요소와 비교 기준이 되는 요소를 비교한다.더 작은 요소가 위치한 인덱스를 min 변수에 저장하면서 계속 min 변수를 갱신해나간다.마지막 위치의 요소까지 비교를 마치고 나면, 최종적으로 min 인덱스에 위치해 있는 요소(arr[min])와 비교 기준이 되는 요소(arr[n])를 서로 교환한다. 시간 복잡도 : O(N²) 버블 정렬, 삽입 정렬과 마찬가지로 시간복잡도가 크기 때문에 효율적인 정렬 알고리즘은 아니다. [예제] 배..

버블 정렬(Bubble Sort) 배열의 이웃한 두 요소의 대소관계를 비교하여 교환을 반복함으로써 이루어지는 정렬 시간복잡도 : O(N²) 배열의 크기가 N개 일 때, 이중 반복문을 사용하기 때문에 N의 제곱만큼의 시간 복잡도가 생긴다. [예제] 배열 arr의 요소가 5 2 3 8 1 4 6 일 때, 배열을 버블 정렬을 통해 오름차순으로 정렬하기 배열의 첫번째 요소부터 인접한 요소와 비교하기 시작한다. 세번째 요소(5)와 네번째 요소(8)는 비교 결과, 5보다 8이 더 크므로 교환하지 않는다. 첫 번째 반복문이 종료되면 배열의 가장 마지막에 8이 위치하게 되고, 마지막 요소는 정렬된 상태가 된다. 두번째는 첫 번째 요소부터 4번째 요소까지 인접한 요소들간의 비교가 이루어진다. 반복문이 종료되면 5번째 위..