CS/DataStructure11 [자료구조] 병합정렬(MergeSort) with JAVA [자료구조] 병합정렬(MergeSort) with JAVA * 병합정렬이란? 병합 정렬은 여러 개의 정렬된 자료의 집합을 결합해 하나의 집합으로 만드는 정렬 방법이다. 이 정렬은 전체를 상대로 수행하지 않고 분할(Divide)한 뒤 각 부분집합들에 대해 정렬한 후 다시 결합(Combine)하는 분할 정복(Divide and Conquer) 기법을 사용한다. * 2-way병합과 n-way 병합 2개의 정렬된 집합을 하나의 집합으로 만드는 병합 방법을 2-way 병합이라고 하고 n개의 정렬된 집합을 결합하여 하나의 집합으로 만드는 방법을 n-way 병합이라고 한다. * 2-way병합 정렬 방법 1) 분할(Divide) : 자료들을 같은 크기의 2개의 부분 집합으로 분할한다. 2) 정복(Conquer) : 부.. 2018. 4. 16. [자료구조] 셸 정렬(Shell Sort) with JAVA [자료구조] 셸 정렬(Shell Sort) with JAVA * 셸 정렬(Shell Sort)이란? 일정한 간격으로 떨어져있는 자료들끼리 집합을 만들어 각각의 집합 내에서 삽입정렬(Insert Sort)을 수행하는 작업을 반복한다. 이 때, 일정한 간격을 세우는 기준 h는 원소 전체의 갯수/2 를 시작으로 하여 한 단계가 수행될 때마다 그 값을 반으로 감소시킨다. 이를 반복 수행하다보면 결국 h가 1이 될 때까지 반복하며 정렬을 마치게 된다. 전체 원소에 대하여 삽입 정렬을 수행하는 것보다 부분집합으로 정렬을 하면 비교 연산과 교환 연산의 횟수를 줄일 수 있다. * 예제 정렬되지 않은 수 {69,7,30,3,16,9,31,23} 를 셸 정렬을 이용하여 정렬하도록 하자. 1) 우선 매개변수 h는 8/2를 .. 2018. 4. 15. [자료구조] 삽입정렬(InsertSort) with JAVA [자료구조] 삽입정렬(InsertionSort) with JAVA * 삽입정렬이란? 삽입정렬은 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법이다. 정렬할 자료가 두 개의 부분집합 S와 U로 나뉘어 있다고 가정한다. 맨 앞 원소부터 정렬을 수행하는데 맨 앞 원소는 집합 S, 나머지는 U로 칭한다. U의 첫번째 원소와 맨 앞 원소인 집합 S에 들어있는 원소를 비교하고 집합 S에 있는 원소와 비교하여 정렬한다. 반복적으로 정렬되지 않은 U 집합의 원소들을 S집합의 마지막 원소, 그 앞 원소, 앞앞 원소들과 반복적으로 비교한다. * 예시 1) 시작 - 첫 번째 원소는 정렬된 부분집합 S로 생각하고 나머지 원소는 정렬 안된 부분 집합 U라고 가정 63 13 28 2 15 7 30 23 .. 2018. 4. 14. [자료구조] 퀵 정렬(Quick Sort) with JAVA [자료구조] 퀵 정렬 with JAVA * 퀵 정렬이란? - 퀵 정렬(Quick Sort)은 정렬할 전체 값들을 정렬을 수행하지 않고 기준값을 중심으로 왼쪽 부분집합과 오른쪽 부분집합으로 분할한다. - 왼쪽 부분 집합에는 기준값보다 작은 원소들을, 오른쪽 부분집합에는 기준값보다 큰 원소들을 이동. - 이 때 사용하는 기준값 = Pivot(피봇) 이라고 칭한다. *퀵 정렬의 핵심 1) 분할 : 정렬할 자료들을 기준값을 중심으로 2개의 부분집합으로 분할한다. 2) 정복 : 기준보다 작은 값은 왼쪽, 기준보다 큰 값은 오른쪽 부분집합으로 정렬, 부분집합의 크기가 1 이하가 아니면 순환 호출을 이용해 다시 분할. *퀵 정렬 방법 Pivot을 중심으로 L 과 R 값을 지정해준다. L은 Pivot보다 큰 값, R은.. 2018. 4. 12. 이전 1 2 3 다음
