[9]
정렬알고리즘
1. 내부 정렬: 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용.
2. 외부 정렬: 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없을때
사용.
1. 버블 정렬
이웃한 두 요소의 대소 관계를 비교하여 교환을 반복
#define swap (type, x, y) do { type t=x; x=y; y=t; } while(0)
void bubble(int a[], int n){
int k=0;
while(k<n-1){
int j;
int last = n-1;
for(j=n-1; j>k; j--)
if(a[j-1] > a[j]{
swap(int, a[j-1], a[j]);
last = j; // 마지막으로 교환을 수행한 위치저장
}
k=last;
}
}
2. 단순 선택 정렬
가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘
#define swap (type, x, y) do { type t=x; x=y; y=t; } while(0)
void selection(int a[], int n){
int i,j;
for(i=0; i<n-1; i++){
int min=i;
for(j=i+1; j<n; j++){
if(a[j]<a[min]) min=j;
swap(int, a[i], a[min]);
}
}
}
3. 단순 삽입 정렬
선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하여 정렬하는 알고리즘.
void insertion(int a[], int n){
int i,j;
for(i=1; i<n; i++){
int tmp=a[i];
for(j=i; j>0 && a[j-1] >tmp; j--)
a[j] = a[j-1];
a[j] = tmp;
}
}
4. 셸 정렬
단순 삽입 정렬의 장점을 살리고 단점을 보완하여 더 빠르게 정렬하는 알고리즘
void shell(int a[], int n){
int i,j,h;
for(h=n/2; h>0; h/=2)
for(i=h; i<n; i++){
int tmp=a[i];
for(j=i-h; j>=0; && a[j] > tmp; j-=h)
a[j+h] = a[j];
a[j+h] = tmp;
}
}
위 코드는 n=8 개의 요소에서 h(증분값)을 h=4, h=2, h=1로 설정하여
1. 2개 요소에 대해 4-정렬(4개그룹) 예) { a[0], a[4]}, {a [1], a[5] }, ...
2. 4개 요소에 대해 2-정렬(2개그룹) 예) { a[0], a[2],a [4], a[6] }, { ...
3. 8개 요소에 대해 1-정렬(1개그룹)
Author And Source
이 문제에 관하여([9]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ucaforens/algorithmdata-structure9저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)