프로그래밍/알고리즘 (5) 썸네일형 리스트형 [알고리즘] 1_4. 병합 정렬(Merge Sort) 1. 정의병합정렬(Merge Sort)는 Divide and Conquer(분할정복) 알고리즘으로 분류되며, 일반적이고 간단한 방법으로 최대, 최악의 경우에도 O(nlogn)의 속도로 sort가 가능하다. Divide and Conquer로 제안된 Merge Sort 알고리즘은 Top-down 방식으로 구현되었다.(후에 Bottom-up 방식의 알고리즘도 발표되었다.) 정렬 방식은 전체의 원소를 1개 원소의 단위로 분할한 뒤, 다시 병합과정을 거쳐 새롭게 정렬된 배열을 생성한다. 같은 평균 속도 O(nlogn)를 가지는 Quick Sort, Heap Sort와 함께 실제로 사용한 경우, 비교적 느리다.(Quick>Heap>Merge 순서) Array의 정렬보다는 Linked List의 정렬에 주로 사용된.. [알고리즘] 1_3. 선택 정렬(Selection Sort) 1. 정의선택 정렬(Selection Sort)이란, 현재 선택된 데이터 이후의 정렬 되지 않은 데이터 중에서 가장 작은(혹은 가장 큰) 데이터를 선택해 현재의 데이터와 위치를 교환하는 방식으로 정렬되는 방식이다. 2. 설명PASS 1우선 가장 앞의 데이터가 선택되게 된다. 그리고 그 데이터 이후를 탐색해 가장 작은 데이터를 찾는다. 최소 값의 데이터를 찾았다면, 두 데이터의 위치를 교환해준다. 예시의 데이터에서는 4 와 1 의 위치를 교환해주게 된다. PASS 2두 번째에서는, 2 가 선택되게 된다. 선택된 이후의 데이터에서 2 보다 작은 값은 존재하지 않으므로, SWAP 과정이 존재하지 않고 완료될 것이다. PASS 3PASS 3에서도 PASS 1, PASS 2와 동일한 방법을 시행한다. PASS 4.. [알고리즘] 1_2. 버블정렬(Bubble Sort) 1. 정의 버블 정렬(Bubble Sort)은 정렬될 때 그 모습이 마치 거품이 위로 하나씩 오르는 듯하다고 해서 이름이 붙여졌다. 원리와 코드가 간단하기 떄문에, 정렬 알고리즘을 배울 때 많이 쓰이는 듯 하다. 버블 정렬의 가장 중요한 원리는 다음과 같다. - 인접한 두개의 데이터를 비교해 가장 큰(혹은 작은) 데이터를 오른쪽에 오도록 위치를 바꾼다. 위 과정을 반복하면, 가장 오른쪽에는 가장 큰(혹은 작은) 데이터부터 쌓이게 된다. 이를 이용해 데이터를 정렬하는 과정을 버블 정렬(Bubble Sort)라고 한다. 2. 설명 PASS 1 버블 정렬은 항상 인접한 두개의 데이터를 비교해가며, Swap을 통해 자료를 정렬한다. 그 순서를 보면 다음과 같다. 우선 2 와 3 을 비교해본다. 3 이 2 보다 .. [알고리즘] 1_1. 삽입정렬(Insertion Sort) 1. 정의 삽입 정렬(Insertion Sort)는 비교적 간단한 정렬 방법 중 하나이다. 삽입 정렬에서의 가장 중요한 규칙은 다음과 같다. - 현재 선택된 데이터 이전의 데이터들은 항상 정렬된 상태이다. 좀 더 알기 쉽게 그림으로 표현하자면, 다음과 같을 것이다. 이를 만족하는 상태로 데이터를 재정렬하는 과정을 삽입 정렬(Insertion Sort)라고 한다. 2. 설명 PASS 1삽입정렬은 두번째 Index부터 시작된다. 제일 앞의 원소는 원소가 하나이기 때문에, 그 자체로 정렬된 상태이기 때문이다. 우선, 4 와 2 의 크기를 비교해, 4 > 2 이므로, 2의 위치를 찾아 삽입해준다. PASS 2두번째로 5 가 선택된다. 5 앞의 정렬된 데이터의 최대값 4 보다 5 가 크므로, 현위치에 둔다. PA.. [알고리즘] 1. 정렬 1. 정의 정렬(Sort)이란 주어진 데이터를 일정한 규칙에 따라 재배열하는 것을 의미한다. 일반적으로 우리는 데이터를 정렬할 때, 오름차순(Ascending) 혹은 내림차순(Descending)으로 정렬 가능하다. 정렬 알고리즘은 많은 것들이 있는데, 현재도 꾸준히 제안되고 발전되고 있다. 많은 정렬 알고리즘들은 데이터의 양, 데이터의 초기 배열 상태 등에 따라서 그 성능이 달라지므로, 상황에 알맞은 정렬법이 필요하다. 2. 종류 1) 삽입 정렬(Insertion Sort) 현재 선택된 데이터를 정렬된 데이터 부분에서 위치를 찾아 '삽입'과정을 통해 정렬하는 방법이다. 성능은 평균적으로 O(n^2)이다. 다만 어느 정도 정렬된 데이터인 경우 매우빠른 속도를 자랑한다. >_본문으로 2) 버블 정렬(Bub.. 이전 1 다음
