이야기박스
우선순위 큐) 삽입정렬(Insertion Sort) & 선택정렬(Selection Sort) 본문
Computer & Data/Algorithm
우선순위 큐) 삽입정렬(Insertion Sort) & 선택정렬(Selection Sort)
박스님 2017. 7. 15. 13:44반응형
두 정렬 알고리즘 모두 Priority Queue의 개념을 이용합니다.
§ Priority Queue ADT란?
데이터 항목이 자유롭게 삽입될 수 있는 저장소, 삭제는 키 값에 의해 결정된다.
여기서 키란 가장 작은것 혹은 큰것 과 같이 기준을 제시해줌.
두 정렬을 요약하자면 아래와 같습니다.
- 삽입 정렬은 리스트의 값이 자신의 위치를 찾아서 들어가는 것.
- 선택 정렬은 주어진 위치에 알맞은 값을 찾아서 넣는 것.
§ 분석
- 두 정렬 모두 O()의 전체적인 수행시간을 갖는다.
- 기존의 리스트를 제외하면 O(1)의 추가 상수공간만 있으면 된다.
§ 간단한 C 구현 코드
#include <stdio.h> #include <stdlib.h> #include <time.h> #define SIZE 100 void selection(int *arr); void insertion(int *arr); int main(void) { int *testArr, *testArr2; // 정렬되지 않은 리스트 testArr = (int *)malloc(sizeof(int)*SIZE); testArr2 = (int *)malloc(sizeof(int)*SIZE); // 시간 세팅 널값 srand(time(NULL)); // 1~100 사이의 값으로 초기화 for (int i = 0; i < SIZE; i++) { testArr[i] = (int)(((double)rand() / (double)RAND_MAX * 100 + 1)); testArr2[i] = (int)(((double)rand() / (double)RAND_MAX * 100 + 1)); } printf("** 삽입 정렬 테스트\n"); // 초기화된 리스트 (랜덤 리스트) printf("* 정렬 전의 리스트\n"); for (int i = 0; i < SIZE; i++) printf(" %d", testArr[i]); // 삽입 정렬 (오름차순) printf("\n* 정렬 후의 리스트 (오름차순) \n"); insertion(testArr); for (int i = 0; i < SIZE; i++) printf(" %d", testArr[i]); printf("\n\n** 선택 정렬 테스트\n"); // 초기화된 리스트 (랜덤 리스트) printf("* 정렬 전의 리스트\n"); for (int i = 0; i < SIZE; i++) printf(" %d", testArr2[i]); // 선택 정렬 (내림차순) printf("\n* 정렬 후의 리스트 (내림차순) \n"); selection(testArr2); for (int i = 0; i < SIZE; i++) printf(" %d", testArr2[i]); free(testArr); free(testArr2); return 0; } void insertion(int *arr) { int save; // 이번 턴의 체크할 값 int i, j; for (i = 1; i < SIZE; i++) { save = arr[i]; j = i - 1; // 기존의 체크한 값들을 비교 // save 보다 크면 하나씩 뒤로 민다 // => save가 들어갈 위치를 찾는 과정 while (j >= 0 && arr[j] > save) { arr[j + 1] = arr[j]; --j; } arr[j + 1] = save; } } void selection(int *arr) { int maxLoc; // 가장 큰 값의 위치 int i, j; int tmp; // 하나 남은 경우는 더 실행할 필요가 없다. for (i = 0; i < SIZE - 1; i++) { maxLoc = i; for (j = i + 1; j < SIZE; j++) { if (arr[j] > arr[maxLoc]) maxLoc = j; } // swap tmp = arr[i]; arr[i] = arr[maxLoc]; arr[maxLoc] = tmp; } }
§ 실행 화면
반응형
'Computer & Data > Algorithm' 카테고리의 다른 글
정렬 알고리즘 정리 (0) | 2017.11.04 |
---|---|
분할 통치) 퀵 정렬 (Quick Sort) (0) | 2017.11.04 |
분할 통치) 합병 정렬 (Merge sort) (0) | 2017.10.20 |
분할통치법 (Divide and Conquer) (0) | 2017.10.20 |
우선순위 큐) 힙 정렬 (0) | 2017.10.14 |