Algorithm5 퀵 정렬(Quick Sort) 퀵 정렬 정렬할 전체 원소에 대해서 정렬을 수행하지 않는다.먼저 기준 값을 중심으로 전체 원소들을 왼쪽 부분집합과 오른쪽 부분집합으로 분할한다.왼쪽 부분집합에는 기준 값보다 작은 원소들을 이동시키고오른쪽 부분집합에는 기준 값보다 큰 원소들을 이동시킨다. 1단계가장 왼쪽의 원소를 기준 값(Pivot)으로 정한후왼쪽에서는 기준 값(27)보다 큰 원소(37)를, 오른쪽에서는 기준 값보다 작은 원소(18)를 찾는다. 두 원소의 자리를 바꾼다. 계속 진행하여 기준 값(27)보다 큰 원소(62)와 작은 원소(16)을 찾는다. 마찬가지로 두 원소의 자리를 바꾼다. 또 다시 반복하여 기준 값(27)보다 큰 원소(59)와 작은 원소(12)를 찾는다.하지만 R 2015. 7. 6. 합병 정렬(Merge Sort) 합병 정렬 여러 개의 자료의 집합을 결합하여 한 개의 정렬된 집합으로 만든다. 1단계자료의 갯수가 하나가 될 때까지 반으로 쪼갠다. 자료의 갯수가 하나가 되면 쪼개는 작업을 멈춘다. 2단계하나씩 정렬을 하면서 합친다. 시간복잡도 Best, Worst, Average 실행코드 / 결과 실행결과를 보면 알 수 있듯이 재귀함수를 사용했기 때문에전부 쪼갠 후 한 번에 합치는 것이 아니라 쪼개고 합치는 과정이 반복되는 것을 확인할 수 있다. 2015. 7. 5. 버블 정렬(Bubble Sort) 버블정렬 인접한 두개의 원소를 비교하여 자리를 교환하는 방식으로첫번째 원소부터 마지막 원소까지 반복하면서 가장 큰 원소를 마지막 자리로 정렬한다. 1단계69와 10의 크기를 비교한 후 자리를 바꾼다. 69와 30의 크기를 비교한 후 자리를 바꾼다. 69와 2의 크기를 비교한 후 자리를 바꾼다. 69와 16의 크기를 비교한 후 자리를 바꾼다. 1단계가 마무리되면 69는 자신의 위치를 찾게 된다. 2단계10과 30의 크기를 비교한다. 10 < 30 이므로 자리를 바꾸지 않는다. 30과 2의 크기를 비교한 후 자리를 바꾼다. 30과 16의 크기를 비교한 후 자리를 바꾼다. 2단계가 마무리 되면 30은 자신의 자리를 찾게 된다. 3단계10과 2의 크기를 비교한 후 자리를 바꾼다. 10과 16의 크기를 비교한 후.. 2015. 7. 1. 삽입 정렬(Insertion Sort) 삽입정렬 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,자신의 위치를 찾아 삽입한다. 1단계69와 10을 비교한 후 정렬한다. 2단계30의 자리를 찾기 위해 먼저 69와 크기를 비교한다. 30 < 69 이므로 10과 30을 비교한 후 정렬한다. 3단계2의 자리를 찾기 위해 먼저 69와 크기를 비교한다. 2 < 69 이므로 그 다음으로 30, 10과 계속해서 비교해나간다.비교한 후 정렬한다. 4단계마찬가지로 69부터 시작해서 차례로 16과 비교한 후 정렬한다. 시간복잡도 Worst, Average Best 실행코드 / 결과 2015. 7. 1. 선택 정렬(Selection Sort) 선택정렬 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬한다.전체 원소 중에서 가장 작은 원소를 찾아서 선택하고 기준 원소와 자리를 교환하는 방식이다. 1단계가장 작은 원소 2를 찾은 후 69와 자리를 바꿔준다. 2단계2를 제외하고 가장 작은 원소 8을 찾은 후 10과 자리를 바꿔준다. 3단계2와 8을 제외하고 가장 작은 원소 10을 찾은 후 30과 자리를 바꿔준다. 4단계2와 8, 10을 제외하고 가장 작은 원소 16을 찾은 후 69와 자리를 바꿔준다. 5단계2와 8, 10, 16을 제외하고 가장 작은 원소 30을 찾은 후 69와 자리를 바꿔준다. 시간복잡도 Best, Worst, Average 2015. 6. 30. 이전 1 다음 728x90
