*성* 스토어

*성*

개인

팔로워0 팔로우

소개

등록된 소개글이 없습니다.

전문분야 등록된 전문분야가 없습니다.

판매자 정보

학교정보

입력된 정보가 없습니다.

직장정보

입력된 정보가 없습니다.

자격증

입력된 정보가 없습니다.

판매지수

판매중 자료수

1개
전체 판매량

8개
최근 3개월 판매량

0개
자료후기 점수

-
자료문의 응답률

-

전체자료 1개

[컴퓨터]정렬탐색 종류 및 알고리즘

정렬의 종류 및 알고리즘(1) 버블 정렬한 원소와 바로 옆 원소끼리만 비교를 해서 순서가 거꾸로이면 위치를 맞바꾸는 대입만 죽어라고 하는 알고리즘입니다. 시간 복잡도는 O(n^2)이며, 거품 정렬은 같은 O(n^2)급 알고리즘 중에서도 상당히 비효율적인 축에 속합니다. 이 알고리즘의 동작 모습을 그래픽 (x, y)->(x, 배열의 x째 원소의 값)으로 시연해 보면 대각선 부위에서 점들이 거품처럼 부글부글 움직이는 모습을 볼 수 있습니다.한 루프를 도는 동안 교환 연산이 한 번도 일어나지 않았다면 자료가 이미 다 정렬되어 있다는 뜻이므로, 그것을 감지하고 실행을 끝내기 위해서 flag라는 변수를 두었습니다.버블정렬 알고리즘void bubbleSort(int iLengthofArray, int *iArray);void main(int argc, char *argv[]){// 프로그램에 사용할 변수.// iArray[]는 리스트를 저장하는 배열, iLengthofArray는 배열에 들어있는 숫자의 갯수int iArray[MAXARRAY], iLengthofArray;FILE *read, *write;// 커맨드 라인에 필요인자가 없을경우 경고메세지와 함께 프로그램 종료if (argc < 2){printf("Usage :exit(0);}// 입력파일이 이상할 경우 경고메세지와 함께 프로그램 종료if ((read = fopen(argv[1], "r")) == NULL){printf("Can't openexit(1);}// 파일로 부터 입력을 받으면서 입력받은 수를 한번 보여줌for (iLengthofArray = 0; (fscanf(read, "%d", &iArray[iLengthofArray])) != EOF && iLengthofArray < MAXARRAY; iLengthofArray++)printf("// 입력 파일 닫기fclose(read);// 입출력 구분선printf("nnn---------------------------------------------------------------------------nnn");// mergeSort 함수 실행bubbleSort(iLengthofArray, iArray);// 출력 파일 생성write = fopen("sorted.txt", "w");// 화면에 정렬된 리스트를 보여주면서 파일에 출력for (int i = 0; i < iLengthofArray; i++){printf("fprintf(write, "}// 출력 파일 닫기fclose(write);}// bubbleSort 함수의 정의 부분void bubbleSort(int iLengthofArray, int *iArray){for (int i = 0; i < iLengthofArray - 1; i++)for (int j = i + 1; j < iLengthofArray; j++)if (iArray[i] > iArray[j]){int iTemp = iArray[i];iArray[i] = iArray[j];iArray[j] = iTemp;}}(2) 선택 정렬가장 큰 값부터 차례대로 리스트의 끝으로 옮겨서 뒤에서부터 앞으로 정렬하는 방법으로, 실제 상황에서 가장 코딩하기 쉽고 직관적인 알고리즘입니다. 수행 시간이 데이터 상태의 영향을 잘 받지 않고, 데이터의 대입 횟수가 적은 게 특징입니다. 거품 정렬보다 2~3배 정도 빠릅니다.선택 정렬 알고리즘void SelectionSort(int A[], int n){int i, j, min;for (i=0; i < n-1; i++){min = i;for (j=i+1; j < n; j++)if (A[j] < A[min]) min = j;temp = A[min];A[min] = A[i];A[i] = temp;}}(3) 삽입 정렬각 원소들에 대해 자기보다 앞에 있는 원소들을 살펴서 순서가 어긋나 있으면 자신을 거기로 옮기고 원래 있던 원소들은 뒤로 한 칸씩 밀어냅니다. 선택 정렬보다 두 배 정도 빨라서 평균적인 성능이 O(n^2) 알고리즘들 중에서 뛰어난 축에 들기 때문에, 이 정렬은 다른 정렬 알고리즘의 일부로도 자주 사용됩니다. 이 방법은 대입이 많으며, 데이터의 상태, 데이터 한 개의 크기에 따라 성능 편차가 심한 편입니다.삽입 정렬 알고리즘void insertion_sort(){int i, j, v;for ( i = 2 ; i v ) {data[j] = data[j-1];j--;}data[j] = v;}}(4) 쉘 정렬삽입 정렬을 일정한 간격으로 띄엄띄엄 수행한 뒤(예를 들어 d=40, 13, 4, ...점차 조밀하게), 전체적으로는 대부분 정렬되어 있는 그 결과 역시 삽입 정렬로 종합합니다(d=1). 이 알고리즘은 삽입 정렬의 특성을 응용한 것뿐인데 삽입 정렬과는 비교할 수 없을 정도로, O(n log n) 알고리즘에 버금가는 성능을 자랑합니다. 부가적인 메모리도 전혀 필요없어서 비용 대 성능도 대단히 뛰어납니다.하지만 이 알고리즘은 '띄엄띄엄'을 어떻게 설정하는게 가장 좋을지가 엄밀하게 알려져 있지 않아 시간 복잡도를 O(n^2)나 O(n log n)처럼 정확하게 계산하기 힘듭니다. 다만, 그 띄엄띄엄 수열이 서로 소가 되게 정의해야 성능이 좋아진다는 것이 알려져 있지요.쉘 정렬 알고리즘void Shellsort(int A[], int N){int i, j, Increment;int Tmp;for(Increment=N/2; Increment>0; Increment/=2)for(i=Increment; i=Increment; j-=Increment)if(Tmp < A[j-Increment])A[j]=A[j-Increment];elsebreak;A[j]=Tmp;}}(5) 퀵 정렬가장 유명하고, 정렬 알고리즘의 표준이다시피 한 방법입니다. 이 알고리즘을 보면 정말 사기-_-라는 생각이 듭니다. 실제로 코딩을 해 보면, 퀵 정렬이 코드가 가장 긴데, 실행 시간은 퀵 정렬이 다른 알고리즘들보다 기막힐 정도로 짧습니다. 중간값이라는 뭔가 적당한(모호한) 값을 선택해야 하고, 최악의 경우 시간 복잡도가 O(n^2)에 메모리 복잡도가 O(n)이 될 가능성까지 있는 알고리즘이 어쩜 이럴 수 있을까요? 하지만 반대로 말하면 퀵 정렬은 자료가 이미 정렬되어 있는 상태를 파악하는 그 민감도를 극대화했기 때문에 이만치 빠를 수 있습니다.중간값을 기준으로 데이터를 반으로 갈라 놓고, 양측에 대해서 재귀적으로 또 중간값을 설정해 정렬을 또 수행한다는 발상은 대단히 깔끔하고 멋집니다. 이런 걸 분할 정복법이라고 하지요. 이게 '퀵 정렬'이 아니었으면 '이분 검색'을 따라 '이분 정렬'이라는 이름이 붙었을 것입니다.퀵 정렬은 본디 재귀적으로 정의되지만, 사용자 정의 스택을 구현해서 비재귀적으로 만들 수도 있으며, 본 소스 코드 역시 사용자 스택을 구현했습니다. 또한, 원소 개수가 한 자리 수로 떨어졌을 때는 또 재귀호출을 하는 게 아니라 삽입 정렬을 해서 능률을 극대화하기도 합니다.퀵 정렬 알고리즘#include #include #define MAXARRAY 100// quickSort 함수의 프로토타입 선언void quickSort(int *iArray, int iTop, int iBottom);void main(int argc, char *argv[]){// 프로그램에 사용할 변수.// iArray[]는 리스트를 저장하는 배열, iLengthofArray는 배열에 들어있는 숫자의 갯수int iArray[MAXARRAY], iLengthofArray;FILE *read, *write;// 커맨드 라인에 필요인자가 없을경우 경고메세지와 함께 프로그램 종료if (argc < 2){printf("Usage :exit(0);}// 입력파일이 이상할 경우 경고메세지와 함께 프로그램 종료if ((read = fopen(argv[1], "r")) == NULL){printf("Can't openexit(1);}// 파일로 부터 입력을 받으면서 입력받은 수를 한번 보여줌for (iLengthofArray = 0; (fscanf(read, "%d", &iArray[iLengthofArray])) != EOF && iLengthofArray < MAXARRAY; iLengthofArray++)printf("// 입력 파일 닫기fclose(read);// 입출력 구분선printf("nnn---------------------------------------------------------------------------nnn");// quickSort 함수 실행quickSort(iArray, iLengthofArray - 1, 0);// 출력파일 생성write = fopen("sorted.txt", "w");// 화면에 정렬된 리스트를 보여주면서 파일에 출력for (int i = 0; i < iLengthofArray; i++){printf("fprintf(write, "}// 출력파일 닫기fclose(write);}// quickSort함수 정의 부분void quickSort(int *iArray, int iTop, int iBottom){// iMid : 피벗 항목보다 큰 수와 작은수를 구분하는 지점을 가리키는 인덱스int iMid = iBottom;// iTemp 두 수를 서로 바꿀때 필요한 임시 저장 공간int iTemp;// 리스트의 상단을 가리키는 숫자가 하단을 가리키는 숫자보다 크면 실행if (iTop > iBottom){for (int i = iBottom + 1; i

공학/기술| 2005.11.26| 13페이지| 1,000원| 조회(825)

알고리즘, 정렬 알고리즘, 탐색종류

미리보기

닫기