Programming/DS SorceCode 썸네일형 리스트형 Sorting.h : 다양한 정렬을 포함한 헤더 | 정렬 방법의 성능 비교 알고리즘 최선 평균 최선 삽입 정렬 선택 정렬 버블 정렬 셸 정렬 퀵 정렬 힙 정렬 합병 정렬 기수 정렬 | 정렬 알고리즘별 실험 결과 ( 정수 : 60,000개 ) 알고리즘 실행 시간( 단위 : sec) 삽입 정렬 7.348 선택 정렬 10.842 버블 정렬 22.894 셸 정렬 0.056 힙 정렬 0.034 합병 정렬 0.026 퀵 정렬 0.014 #pragma once#ifndef ___Sorting#define ___Sorting// Sorting.h : 다양한 정렬을 포함한 헤더#include "cstdio"#include "cstdlib"#include "CircularQueue.h" #define MAX_SIZE 1024#define BUCKETS 10#define.. 더보기 기수 정렬 프로그램 기수 정렬 다른 정렬방법들은 모두 레코드들을 비교하여 정렬한다. 기수 정렬(radix sort)은 입력 데이터에 대해서 어떤 비교 연산도 실행하지 않고 데이터를 정렬할 수 있는 색다른 정렬 기법이다. 다른 방법들이 이라는 정렬의 이론적인 하한선을 깰 수 없는데비해 기수 정렬은 이 하한선을 깰 수 있는 유일한 기법이다. 사실 기수 정렬은 의 시간 복잡도를 가지는데 대부분 k 더보기 퀵 정렬 알고리즘을 이용해 오름차순으로 정렬하는 함수 퀵 정렬 퀵 정렬(quick sort)은 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 퀵 정렬도 합병 정렬과 같이 분할-정복법(divide and conquer)을 사용한다. 그러나 합병 정렬과는 달리 리스트를 균등하지 않게 분할한다. 먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택한다. 여기서는 리스트의 첫 번째 요소를 피벗으로 하자. 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮기고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮긴다. 결과적으로 피벗을 중심으로 왼쪽은 피벗보다 작은 요소들로 구성되고, 오른쪽은 피벅보다 큰 요소들로 구성된다. 이 상태에서 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하게 되면 전체 리스트가 정렬된다. 퀵 정렬의 평균적인 경우의 시.. 더보기 합병 정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수 합병 정렬 합병 정렬(merge sort) 은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 리스트를 합하여 전체가 정렬된 리스트트를 만드는 방법이다. 이것은 분할 정복(divide and conquer) 기업에 바탕을 두고 있는데, 하나의 문제를 작은 2개의 문제로 분리하고 각가을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분리된 문제가 아직도 해결하기 어렵다면, 즉 충분히 작지 않다면 분할 정복 방법을 연속하여 다시 적용한다. 분할 정복 기법은 대개 순환 호출을 이용하여 구현된다. 1. 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할 한다. 2. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충.. 더보기 셸 정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수 | 셸 정렬의 분석 셸 정렬의 2가지 장점 연속적이지 않은 부분 파일에서 자료의 교환이 일어나면 더 큰 거리를 이동한다. 반면 삽입 정렬에서는 한 번에 한 칸씩만 이동된다. 따라서 교환되는 아이템들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 높아진다. 부분 리스트가 하나가 되면 셸 정렬은 전체 리스트를 정렬해야 한다. 그러나 삽입 정렬이 거의 정렬된 리스트에 대해 매우 효율적이므로 이 과정도 빠르게 수행된다. 실험적인 연구를 통하여 셀 정렬의 시간 복잡도는 최악의 경우에는 이지만 평균적인 경우에는 인 것으로 알려져 있다. // gap 만큼 떨어진 요소들을 삽입 정렬. 정렬의 범위는 first 에서 laststatic void sortGapInsertion(int A[], int first, .. 더보기 버블 정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수 //버블 정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수void bubbleSort(int A[], int n) {for (int i = n - 1; i > 0; i--) {for (int j = 0; j A[j + 1])swap(A[j], A[j + 1]);}} 더보기 함수 포인터를 매개변수로 받는 삽입정렬 함수 inline int ascend(int x, int y) { return y - x; }//오름차순 비교함수inline int descend(int x, int y) { return x - y; }//오름차순 비교함수 // 함수 포인터를 매개변수로 받는 삽입정렬 함수void insertionSortFn(int A[], int n, int(*f)(int, int)){for (int i = 1; i = 0 && f(A[j], key) < 0; j--)A[j + 1] = A[j];A[j + 1] = key;}} 더보기 삽입정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수 - 안정 정렬 //삽입정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수 - 안정 정렬void insertionSort(int A[], int n){for (int i = 1; i = 0 && A[j] > key; j--)A[j + 1] = A[j];// 레코드의 오른쪽으로 이동A[j + 1] = key;}} 더보기 이전 1 2 3 4 5 ··· 8 다음