셸 정렬(Shell Sort)



셸 정렬?

셸 정렬은 Donald Shell이라는 분이 창안해서 이름이 셸 정렬이 되었다고 합니다.


셸 정렬은 삽입정렬의 단점을 보완하기 위해 등장한 정렬방법입니다.

(단점 예 : 내림차순으로 정렬된 항들을 오름차순으로 정렬하려면 모든 항을 계산 해야 하는 점)


효율 적인 삽입 정렬을 위해 특정 기준으로 사전에 정렬을 수행한 후에 삽입정렬을 수행합니다.


사전에 진행하는 정렬은 특정 기준을 정해서 진행합니다.


어떠한 방법?

저는 길이가 10개인 배열을 2로 나누면서 기준을 잡았습니다.


총 크게 3번 정렬을 진행 했습니다.


10/2 = 5, 5/2 = 2(int형이므로 2.5에서 버림처리), 2/2 =1


아래와 같이 배열에 10개의 인자가 있을 때



1번째 정렬은 5개씩 나눠서 각각 비교해서 정렬 합니다.

각 대응되는 항의 크기를 비교해서 정렬을 하면 아래와 같습니다.




2번째 정렬은 2개 전 항과 비교하며 정렬합니다.


2개의 항씩 정렬하고나면 아래와 같습니다.


마지막으로 3번째 정렬은 전체 항을 삽입 정렬 합니다.


배열을 이용한 셸 정렬 예제


셸 정렬 함수


첫번째 for문 : 5개, 2개, 1개씩 비교를 위한 기준 for문,


두번째 for문 : 기준까지만(5,2,1) 반복하기 위한 for문


세번째 for문 : 위 기준대로 반복하는 for문


while문 : 위 그림들 처럼 비교했을 때 작을경우 삽입하는 동작을 수행


void shell_sort(int array[], int size){
for(int i=size/2; i>0; i /=2){
for(int j=0; j<i; j++){
for(int k=i+j; k<size; k+=i){
int l = array[k];
int m = k;
while(m>i-1 && array[m-i] > l){
array[m]=array[m-i];
m -= i;
}
array[m] = l;
}
}
printf("i=%d || ",i);
print_array(array,size);
}
}


배열 출력 함수


void print_array(int array[], int size){
for(int i=0; i<size; i++){
printf("%-4d",array[i]);
}
printf("\n");
}


실행 함수


정렬 전 배열과 위의 기준대로 정렬한 결과를 출력합니다.


void main(){
int array[] = {11,10,33,22,55,9,99,81,15,27};
int size = sizeof(array)/sizeof(int);
printf("########### Sorting before ###########\n");
print_array(array, size);
printf("######################################\n");
shell_sort(array, size);
}


실행 결과


참고 : C로 배우는 알고리즘 (이재규)

위키백과(셸 정렬)


관련 포스팅


[DataStructure] 기수 정렬(Radix Sort)

[DataStructure] 퀵 정렬(Quick Sort)

[DataStructure] 셸 정렬(Shell Sort)

[DataStructure] 버블 정렬(Bubble Sort)

[DataStructure] 삽입 정렬(Insertion Sort)

[DataStructure] 선택 정렬(Selection Sort)





저작자표시 비영리

'언어 > Data Strcuture' 카테고리의 다른 글

[C] 기수 정렬(Radix Sort)  (1) 2019.04.30
[C] 퀵 정렬(Quick Sort)  (0) 2019.04.24
[C] 버블 정렬(Bubble Sort)  (0) 2019.04.20
[C] 삽입 정렬(Insertion Sort)  (0) 2019.04.19
[C] 선택 정렬(Selection Sort)  (0) 2019.04.19

연결리스트(LinkedList)



연결리스트(LinkedList)?

연결리스트는 동적인 자료구조로 배열처럼 메모리에 연속된 공간을 차지하지 않습니다.


1. 단순 연결리스트(Simple LinkedList)


노드와 다음링크를 가리키는 링크로 구성


처음 시작을 의미하는 head와 마지막 노드인 tail로 구성

2. 환형 연결리스트(Circular LinkedList)


가장 마지막 노드가 처음의 노드를 가리키는 연결리스트

3. 이중 연결리스트(Doubly LinkedList)


전, 후 노드를 가리키는 링크를 가지는 연결리스트


단순 연결리스트 예제


구조체 (key, value, 다음을 가리키는 링크로 구성) 선언


typedef struct _node
{
int key; // key
char *value; // value
struct _node *next; // 다음 노드의 위치
} node;
node *head, *tail; // head, tail


초기화 함수

head 와 tail 초기화


void init_list(void){
head = (node*)malloc(sizeof(node));
tail = (node*)malloc(sizeof(node));
head -> next = tail;
tail -> next = tail;
}

노드 삽입 함수
입력받은 노드의 다음에 삽입


node *insert_list(int key, char *value, node *t){
node *s;
s = (node*)malloc(sizeof(node));
s->key = key;
s->value = value;
s->next = t->next;
t->next = s;
return s;
}

노드 삭제 함수
입력받은 노드를 삭제

int delete_list(node *t){
node *s = head;
while(s->next != tail){
if(s->next==t){
s->next = t->next;
free(t);
break;
}else{
s = s->next;
}
}
}

노드 검색 함수
key를 이용해서 원하는 노드를 검색

node *find_node(int key){
node *s = head->next;
while(s != tail->next){
if(key == s->key){
break;
}else{
s = s->next;
}
}
return s;
}


전체 검색 함수

void findAll(){
node * t = head->next;
printf("#########findAll()########\n");
while(t != tail){
printf("find(%d) = %s , address = %d\n",t->key,find_node(t->key)->value,&t->next);
t = t->next;
}
printf("##########################\n");
}

메인 함수
노드 초기화 후 5개 데이터를 추가하고 2개의 데이터 삭제 후 전체 출력

void main(){
init_list();
insert_list(0,"apple",head);
insert_list(1,"banana",find_node(0));
insert_list(2,"melon",find_node(1));
insert_list(3,"grape",find_node(2));
insert_list(4,"pineapple",find_node(3));

delete_list(find_node(2));
delete_list(find_node(1));
findAll();
}

실행 결과


참고 : C로 배우는 알고리즘 (이재규)


관련 포스팅


[Data Strcuture] - 트리(Tree)

[Data Strcuture] - 큐(Queue)

[Data Strcuture] - 스택(Stack)

[Data Strcuture] - 연결리스트(LinkedList)




저작자표시 비영리

'언어 > Data Strcuture' 카테고리의 다른 글

[C] 삽입 정렬(Insertion Sort)  (0) 2019.04.19
[C] 선택 정렬(Selection Sort)  (0) 2019.04.19
[C] 트리(Tree)  (0) 2019.04.07
[C] 큐(Queue)  (2) 2019.04.01
[C] 스택(Stack)  (1) 2019.03.29

+ Recent posts

티스토리툴바