Cohe
정렬 본문
728x90
버블 정렬
버블정렬 : 버블 정렬은 정렬이 진행되는 모양이 비누거품과 같다고 하여 붙여진 이름이다. 나란히 있는 두개의 데이터를 계속하여 바꾸어 나간다.
- 전체 비교 횟수 : T(n)=n(n-1)/2
- 시간 복잡도 : O(n²)
알고리즘
list에 대한 기본 버블정렬 알고리즘
void bubble_sort(element list[], int n){
int i, j;
element next;
for (i=n-1;i>0;i--){
for(j=0;j<i;j++){
if (list[j]>list[j+1]{
swap(list[j],list[j+1]}}}}
개선된 버블정렬
- 버블정렬 각 단계에서 데이터의 이동이 일어나지 않으면 다음 단계로 진행할 필요가 없다. 즉 중간과정에서 정렬이 끝나면 더 이상 비교와 교환이 필요없다.
void bubble_sort(element list[], int n){
int i, j;
element next;
for (i=n-1;flag>0;i--){
flag=0;
for(j=0;j<i;j++){
if (list[j]>list[j+1]{
swap(list[j],list[j+1]
flag=1;}}}}
- 버블 정렬 : 진행 할 수록 뒤에 정렬되어버림 → 완전 끝까지 할 필요는 없는데 그만 할 수 있으면 그만하자! → 교환하면 깃발 들어! 진행 계속!!
- 교환 x → flag 진행 그만!
삽입 정렬
- 각 단계에서 list[j]를 앞 방향으로 비교해가면서 교환해 나간다. 더 작은 값이 나오면 멈춘다. j번째 진행될 때는 앞선 데이터는 정렬이 끝난 상태이다.
- 전체 비교횟수 : T(n)=n(n-1)/2
- 시간 복잡도 : O(n²)
알고리즘
void insertion_sort(element list[], int n){
int i, j;
element next;
for(i=1;i<n;i++){
next=list[i];
for(j=i-1;j>=0;j-- && next.key <list[j].key;j--)
{list[j+1]=list[j];};
list[j+1]=next;
}
}
퀵 정렬
- 정렬 속도가 빠르다.
- 과정
- 리스트에서 기준 데이터 1개를 지정한 다음 리스트의 데이터들을 앞과 뒤 양쪽에서 가운데쪽으로 1개씩 비교하여양쪽에서 비교하여 오기 때문에 이동할 데이터를 찾으면 서로 맞바꾼다.
- 기준 데이터보다 큰 값을 리스트 앞에서 찾아서 리스트의 뒤쪽으로 기준데이터보다 작은 값은 리스트의 뒤쪽에서 찾아서 리스트의 앞 쪽으로 둔다.
- 첫 번째 과정이 끝나면 두 개의 리스트에 대해서 각각 같은 방법으로 첫번째 과정과 같은 방법으로 분리한다.
- 과정
- 전체 비교횟수 : T(n)=n
- 시간 복잡도 : O(nlog2n) → 최악시간은 O(n²){이미 정리되어진 상황}
알고리즘
void quicksort(element list[], int left, int right)
{
int pivot, i, j; element temp;
if(left<right){
i=left; j=right+1;
pivot=list[left].key;
do{
do i++;
while(list[i].key<pivot &&i<=right);
do j--;
while(list[j].key>pivot);
if(i<j)
SWAP(list[i], list[j], temp);
}while(i<j);
SWAP(list[left], list[j], temp);
quicksort(list, left, j-1);
quicksort(list,, j+1, right);
}
}
Q 10.3
힙 정렬
- 힙은 트리중에서 부모 노드의 원소 값이 자식 노드의 원소 값보다 큰 완전 이진트리 이다.
- 힙 구조에서 가잔 큰 값의 위치는 루트에 있으며 가장 작은 값은 리프 노드 중에 있게 된다. 힙은 완전 이진트리이므로 트리 구조이지만 배열에 저장하는 것이 더 효율적이다.
#define MAX_ELEMENTS 200 #define HEAP_FULL(n) (n == MAX_ELEMENTS #define HEAP_EMPTY(n) (!n) typedef struct { int key: } element: element heap[MAX_ELEMENTS]; int n = 0;
- 리스트를 배열에 저장하여 힙을 만든다.
- Adjust 알고리즘(다시 흔들기) 0.5n번 적용하여 완전 이진트리 힙 구성
- 힙에서 n개의 데이터를 삭제하고 힙을 재구성하는 과정을 반복한다.
- Adjust 알고리즘 n-1번 수행
- 시간 복잡도 : O(nlog2n)
- 재구성 : O(h) : h=트리의 깊이.
알고리즘
재구성 알고리즘
void adjust(element list[], int root, int n) {
int child, rootkey; element temp;
temp = list[root];
rootkey = list[root].key;
child = 2 * root; /* left child */
while(child <= n) {
if((child < n) &&
(list[child].key < list[child+1].key))
child++;
if(rootkey > list[child].key) break;
else {
list[child/2] = list[child];
child *= 2;}
}
list[child/2] = temp;
}
알고리즘
void quicksort(element list[], int left, int right)
{
int pivot, i, j; element temp;
if(left<right){
i=left; j=right+1;
pivot=list[left].key;
do{
do i++;
while(list[i].key<pivot &&i<=right);
do j--;
while(list[j].key>pivot);
if(i<j)
SWAP(list[i], list[j], temp);
}while(i<j);
SWAP(list[left], list[j], temp);
quicksort(list, left, j-1);
quicksort(list,, j+1, right);
}
}
Q 10.3
힙 정렬
- 힙은 트리중에서 부모 노드의 원소 값이 자식 노드의 원소 값보다 큰 완전 이진트리 이다.
- 힙 구조에서 가잔 큰 값의 위치는 루트에 있으며 가장 작은 값은 리프 노드 중에 있게 된다. 힙은 완전 이진트리이므로 트리 구조이지만 배열에 저장하는 것이 더 효율적이다.
#define MAX_ELEMENTS 200 #define HEAP_FULL(n) (n == MAX_ELEMENTS #define HEAP_EMPTY(n) (!n) typedef struct { int key: } element: element heap[MAX_ELEMENTS]; int n = 0;
- 리스트를 배열에 저장하여 힙을 만든다.
- Adjust 알고리즘(다시 흔들기) 0.5n번 적용하여 완전 이진트리 힙 구성
- 힙에서 n개의 데이터를 삭제하고 힙을 재구성하는 과정을 반복한다.
- Adjust 알고리즘 n-1번 수행
- 시간 복잡도 : O(nlog2n)
- 재구성 : O(h) : h=트리의 깊이.
알고리즘
재구성 알고리즘
void adjust(element list[], int root, int n) {
int child, rootkey; element temp;
temp = list[root];
rootkey = list[root].key;
child = 2 * root; /* left child */
while(child <= n) {
if((child < n) &&
(list[child].key < list[child+1].key))
child++;
if(rootkey > list[child].key) break;
else {
list[child/2] = list[child];
child *= 2;}
}
list[child/2] = temp;
}
힙정렬
void heapsort(element list[], int n) {
int i, j;
element temp;
for(i = n / 2; i > 0; i--) /*1*/
adjust (list, i, n);
for(i = n - 1; i > 0; i--) { /*2*/
SWAP(list[1], list[i + 1], temp);
adjust (list, 1, i);
}
}