본문 바로가기
반응형

정렬 알고리즘8

qsort 함수에 대하여.. 2007. 4. 3.
퀵 정렬(Quick Sort) 4. 퀵 정렬 퀵 정렬은 C.A.R. Hoare가 만든(The Computer Journal, 5:10-15, 1962.) 가장 우수한 편에 속하는 평균 수행능력을 갖는 정렬 방식이다. (단, 조건에 따라서는 분포수 정렬, 역사상 정렬, 래딕스 정렬방법이 빠르다.)버블정렬이나 선택정렬의 경우, 바로 옆의 데이터를 서로 비교하여 교환하는 방식인데, 이러한 방식은 데이터가 최종으로 정렬될 위치에서 멀면 멀수록 비효율적이라고 할 수 있다. 퀵 정렬은 멀리 떨어진 데이터를 서로 교환함으로써 이러한 비효율성을 개선하였다. 간단히 설명하면, 'Pivot' 이라 불리는 임의의 값을 설정한 후에 배열의 양끝방향에서부터 탐색을 시작해서 Pivot값보다 큰 값과 작은값을 발견하여 서로 치환하는 방식이다. 단점으로는, Pi.. 2007. 4. 3.
쉘 정렬(Shell sort) u 삽입 정렬을 간단하게 변형 u 멀리 떨어진 원소끼리 교환이 가능하게 하여 정렬 속도를 향상시킴 u h-정렬 화일 : 모든 h번째 원소를 정렬한 화일 u 증가 순서의 예 : …, 1093, 364, 121, 40, 13, 4, 1 u 특징 Ø 순열 h가 1, 4, 13, 40, … 일 때, 쉘 정렬의 비교회수는 N 3/2 을 넘지 않음 Ø 안정적인 제자리 정렬 ShellSort(a[], n) for (h ← 1; h 0; h ← h/3) do { // h 값을 감소시키며 진행 for (i ← h + 1; i ≤ n; i ← i+1) do { v ← a[i]; j ← i; while (j >h and a[j-h] >v) do { a[j] ← a[j-h]; j ← j-h; } // while A[j] ← .. 2007. 4. 3.
삽입 정렬(Insertion Sort) ■ 삽입 정렬 개념 • 삽입정렬은 매우 간단한 정렬 방법으로 소량의 자료를 처리하는데 유용 • 파일을 구성하고 있는 부파일(subfile)의 레코드들이 이미 정렬이 되어 있다고 가정 • 한 번에 한 개의 새로운 레코드를 입력하여 정렬되어 있는 사이트의 적당한 위치를 찾아서 레코드를 삽입 • 따라서 새롭게 삽입된 레코드를 포함하여 파일은 항상 정렬된 상태를 유지 ■ 삽입 정렬 과정 ① 두 번째 키를 기준으로 하여 첫 번째 키를 비교하여 키 값에 따라 순서대로 나열 ② 세 번째 키를 기준으로 하여 두 번째 키와 첫 번째 키를 비교하여 키 값에 따라 순서대로 나열 ③ 계속하여 n번째 키를 앞의 n-1개의 키와 비교하여 삽입될 적당한 위치를 찾아 삽입한다. 30 15 20 17 40 ------> 초기상태 30.. 2007. 4. 3.
반응형

티스토리툴바