자료구조
-
[Sort] 셸 정렬(Shell Sort)CSE/Sort 2015. 6. 12. 15:44
셸 정렬(Shell Sort) [출처: 위키] 정의: 일정한 간격으로 떨어져 있는 자료들끼리 부분집합을 구성하고 각 부분집합에 있는 원소들에 대해서 삽입 정렬을 수행하는 작업을 반복하면서 전체 원소들을 정렬 하는 방법 부분 집합을 만드는 기준은 원소 개수의 반으로 나누어서 반복 수행한다. 자 정의는 이정도로 하고 시작할까요?? 1단계 1단계 정렬 전입니다!! 자 먼저 부분 집합을 만들기 위해 원소 갯수 / 2 를 통해 4 라는 숫자를 만들어 둡시다. 4라는 숫자를 기준으로 부분 집합을 만들어 봅시다!! 자 이렇게 나옵니다! 4개의 부분 집합으로 보이시죠?? {69, 16}, {10, 8}, {30, 31}, {2, 22} 이렇게 색깔 별로 다르게 해서 집합을 4개 표현 했습니다!!! 집합을 하고 나면 집..
-
[Sort] 퀵 정렬(Quick sort)CSE/Sort 2015. 6. 12. 15:40
퀵 정렬(Quick Sort) [출처: 위키] 정의: 퀵정렬은 정렬할 전체 원소에 대해서 정렬을 수행하지 않는다. 먼저 기준 값을 중심으로 전체 원소들을 왼쪽 부분집합과 오른쪽 부분집합으로 분할(Divide)한다. 왼쪽 부분 집합에는 기준 값보다 작은 원소들을 이동시키고, 오른쪽 부분 집합에는 기준 값보다 큰 원소들을 이동시킨다. 위의 정의를 잘 이해 하셔야 퀵 정렬이 쉽게 이해 됩니다!!! 1단계 위 처럼 8개의 값을 정렬 합시다!! 저기 보시면 2라는 숫자가 기준 값(Pivot)이 됬는데요... 기준 값을 구하는 법은 배열의 시작 값과 끝 값의 인덱스를 더한 것에서 2를 나눠줍니다. 즉 위에서는 ( 0 + 7 ) / 2 = > 3 이라는 인덱스 값이 나오니깐 배열의 3번째는 2라는 숫자입니다!!! ..
-
[Sort] 삽입 정렬(Insertion sort)CSE/Sort 2015. 6. 12. 15:33
삽입 정렬(Insertion Sort) [출처: 위키] 정의: 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 정의는 위와 같습니다!! 그림으로 보시죠!! 정렬할 배열은 위와 같습니다. 버블버블때 썼던 놈 그대로 합죠!! 1단계: 네. 1 단계는 맨 처음 요소가 부분 집합으로 꾸려져있죠?? 그리고 10 이란 놈이 부분 집합의 놈들과 비교를 해서 들어갈 자리를 물색 합니다... 10 < 69 이므로...! 아래 처럼 정렬이 됩니다! 1단계 끝!!! 2단계: 이번엔 30을 저 안에서 비교를 하여, 30의 자리를 찾아야 합니다! 30의 자리는 딱봐도 10과 69의 사이 겠죠??? 그래서 요 단계에서는 먼저, 30 <..