합병 정렬(Merge Sort)




합병 정렬? 

합병 정렬은 병합 정렬이라고도 불리며, 배열을 여러개로 분할해서 병합하면서 정렬하는 방법입니다.


특징

1) 메모리 내부에서 정렬하는 방법

2) 연결 리스트와 같은 순차적인 접근이 가능한 자료구조에 유일한 정렬 방법


어떠한 방법?

예제는 정렬할 배열과 임시로 담아놓을 배열 2개를 이용해서 정렬을 진행했습니다.


아래와 같은 배열이 있을 때



배열을 나눠서 정렬을 한 뒤 병합하면서 정렬을 진행합니다.





배열을 이용한 합병 정렬 예제


배열 출력 함수


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

병합 정렬 함수


- size : 2씩 곱해지면서 정렬할 항의 수를 결정

- first, second : 하나의 배열을 두개처럼 사용하기위한 변수 각각 비교할 항 앞과 뒤를 가리킴

- i, j : 각각 비교할 앞의 항과 뒤의 항

- k : 임시로 담을 배열의 인덱스


void merge_sort(int a[], int n){
int i, j, k;
int first, second, size;
int *b;
b = (int*)malloc(sizeof(int)*n);
for(size = 1; size<n; size *=2){
first = -2 * size; // 초기 값
second = first + size;
while(second + size*2 < n){
first = second + size;
second = first + size;

i = k = first;
j = second;
while(i<first+size || (j<second+size && j<n)){
if(a[i]<=a[j]){
if(i<first + size)
b[k++] = a[i++];
else
b[k++] = a[j++];
}else{
if(j<second+size && j<n)
b[k++] = a[j++];
else
b[k++] = a[i++];
}
printf(" b[%d]=%d\t",k-1,b[k-1]);
}
printf("\n############################\n");
}
for(i=0; i<n; i++)
a[i] = b[i];
}
free(b);
}



메인 함수


void main(){
int array[] = {6,8,5,2,7,3,1,4};
int size = sizeof(array)/sizeof(int);
printf("########### Sorting before ###########\n");
print_array(array, size);
printf("######################################\n");
merge_sort(array, size);
printf("########### Sorting after ###########\n");
print_array(array, size);
}



실행 결과




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

위키백과(합병 정렬)



관련 포스팅


[DataStructure] 기수 정렬(Radix Sort)

[DataStructure] 퀵 정렬(Quick Sort)

[DataStructure] 셸 정렬(Shell Sort)

[DataStructure] 버블 정렬(Bubble Sort)

[DataStructure] 삽입 정렬(Insertion Sort)

[DataStructure] 선택 정렬(Selection Sort)



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

[C] 힙 정렬(Heap Sort)  (0) 2019.05.01
[C] 기수 정렬(Radix Sort)  (1) 2019.04.30
[C] 퀵 정렬(Quick Sort)  (0) 2019.04.24
[C] 셸 정렬(Shell Sort)  (2) 2019.04.23
[C] 버블 정렬(Bubble Sort)  (0) 2019.04.20

힙 정렬(Heap Sort)




힙(Heap) ?  

최대값, 최소값을 찾아내는 연산을 빠르게 하기위해 고안된 완전트리를 기본으로 한 자료구조


힙정렬

힙 정렬은 분할정복 알고리즘으로 최대 힙 트리나 최소 힙 트리를 구성해 정렬 하는 방법 입니다.


어떠한 방법?

예제는 배열을 이용해서 트리구조를 구성했습니다.


배열을 이용한 트리구조에서 주의할 점은 균형 잡히지 않은 노드의 경우 실제로 없는 노드를 위해 배열 공간을 확보해야 하기 때문에 균형잡힌 노드에 한해서 사용 가능합니다.



아래와 같은 이진트리가 있을 때


A노드부터 1번부터 12번까지 숫자를 매기면 아래 그림과 같습니다.



이 때 i노드의 부모번호는 i/2

i노드의 왼쪽 자식노드는 2i 오른쪽 자식노드는 2i+1을 만족합니다.


예) 5번 노드의 부모노드 번호는 5/2=2(버림)

4번 노드의 왼쪽 자식노드는 4*2=8 오른쪽 자식도느는 4*2+1 = 9


이 개념을 이용하면 배열을 이용해서 트리를 구성할 수 있습니다.



배열을 이용한 힙 정렬 예제


upHeap함수


아래에서 위로 올라가면서 자리를 바꾸는 함수입니다.


void upHeap(int array[], int k){
int v;
v = array[k];
array[0] = MAX;
while (array[k/2]<=v) // 부모 <= 자식
{
array[k] = array[k/2];
k/=2;
}
array[k] = v;
}


downHeap함수


upHeap함수와 반대로 아래로 내려가면서 비교하는 함수입니다.

자식노드 왼쪽과 오른쪽 노드를 비교해서 더 큰 노드를 이용합니다.


void downHeap(int array[], int n, int k){
int i;
int v = array[k];
while(k<=n/2){
i = k<<1; // 2*k
if(i<n && array[i]<array[i+1]) i++; //왼쪽, 오른쪽 노드 비교
if(v>=array[i]) break;
array[k] = array[i];
k=i;
}
array[k] = v;
}


insert, delete함수


insert는 입력받은 배열을 트리구조로 사용하기 위해 입력하는 함수

delete는 정렬된 데이터를 받아오는 함수 입니다.


void insert(int array[], int *hn, int v){
array[++(*hn)] = v;
upHeap(array, *hn);
}

int delete(int array[], int *n){
int v = array[1];
array[1] = array[(*n)--];
downHeap(array, *n, 1);
return v;
}


힙 정렬 함수


입력받은 배열을 정렬하는 함수입니다.


첫번 째 for문 : 배열을 순차적으로 삽입

두번 째 for문 : 정렬된 데이터를 꺼냄

마지막 for문 : 정렬시에 0번째에는 큰 수를 넣어놓고

1번째 인덱스부터 이용했기 때문에 

한칸씩 당겨주는 for문


void heap_sort(int array[], int n){
int hn = 0;
int i= 0;
for(i=1; i<=n; i++)
insert(array, &hn, array[i]);
for(i=hn; i>=1; i--){
array[i] = delete(array, &hn);
}
for(int j=0; j<n; j++){
array[j] = array[j+1];
}
}


배열 출력 함수


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


메인 함수


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

정렬을 하고나면 배열의 크기가 변하기 때문에
oldSize변수에 초기 크기를 저장해두고 진행했습니다.

void main(){
int array[] = {11,1,83,202,55,4,119,81,15,47,19,28};
int oldSize = sizeof(array)/sizeof(int);
int size = sizeof(array)/sizeof(int);
printf("########### Sorting before ###########\n");
print_array(array, size);
heap_sort(array, size);
printf("########### Sorting after ###########\n");
print_array(array, oldSize);
}

실행 결과




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

  위키백과(힙 ,힙 정렬)



관련 포스팅


[DataStructure] 기수 정렬(Radix Sort)

[DataStructure] 퀵 정렬(Quick Sort)

[DataStructure] 셸 정렬(Shell Sort)

[DataStructure] 버블 정렬(Bubble Sort)

[DataStructure] 삽입 정렬(Insertion Sort)

[DataStructure] 선택 정렬(Selection Sort)





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

[C] 합병 정렬(Merge Sort)  (0) 2019.05.04
[C] 기수 정렬(Radix Sort)  (1) 2019.04.30
[C] 퀵 정렬(Quick Sort)  (0) 2019.04.24
[C] 셸 정렬(Shell Sort)  (2) 2019.04.23
[C] 버블 정렬(Bubble Sort)  (0) 2019.04.20

기수 정렬(Radix Sort)




기수정렬?

기수정렬은 자리수별로 비교하여 정렬하는 방법입니다.


비교연산은 하지않고, 정수와 같은 자료의 정렬 속도가 매우 빠릅니다.


복잡도

가장 큰 숫자의 자리수가 d라고할 때 복잡도는 아래와 같습니다.





아래와 같은 배열이 있을 때 


가장 큰 숫자의 자리수는 3이므로 정렬을 3번 진행합니다.


각 자리수에 해당하는 큐에 순서대로 데이터를 삽입합니다.


가장먼저 1의자리 정렬입니다.



1의자리를 기준으로 정렬된 데이터를 

10의자리 기준으로 정렬합니다.



마지막으로 10의자리 기준으로 정렬된 데이터를

100의자리 기준으로 정렬합니다.


정렬한 데이터를 큐에서 전부 꺼내주면 정렬이 완료됩니다.



큐를 이용한 기수 정렬 예제


많은 예제들을 찾아봤는데, 0~9 총 10개의 큐를 만들어서 진행하는 예제가 많았습니다.


굳이 10개의 큐가 필요할까? 라는 생각을 하게 되었고, 큐 하나만 이용해서 정렬을 진행해 봤습니다.



Queue put(),get()함수 


Queue관련 내용은 생략하겠습니다.


Queue관련 내용은 아래 포스팅 참고바랍니다.


[Data Strcuture] 큐(Queue)



#include <stdio.h>
#define MAX 20
// QUEUE

int queue[MAX];
int front, rear = 0;

int put(int k){
if((rear+1) % MAX == front){
printf("QUEUE OVER FLOW!\n\n");
return -1;
}else{
queue[rear] = k;
rear = ++rear % MAX;
return 1;
}
}

int get(){
int k;
if(front == rear){
printf("QUEUE UNDER FLOW!\n\n");
return -1;
}else{
k = queue[front];
front = ++front % MAX;
return k;
}
}

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


기수정렬 함수


가장 큰 숫자를 찾아서 자리수를 구한 뒤


0~9까지 각 자리에 맞는 숫자가 나올때 큐에 삽입하고


반복이 끝나면 큐에서 배열에 담고 큐를 초기화 하는 방법으로 진행 했습니다.


void radix_sort(int array[], int size){
int max = array[0];
int digit = 0;
int factor = 1;
for(int i=1; i<size; i++){
if(max<array[i]) max = array[i];
}
for(int i=max; i>0;i/=10){
digit++;
}

for(int i =0; i<digit; i++){
for(int j=0; j<10; j++){ // 0~9
for(int k=0; k<size; k++){
if((array[k]/factor)%10==j){
put(array[k]);
}
}
}
factor *=10;
for(int i=front; i!=rear; i++){
array[i] =get();
}
printf("########### %d ROUND ###########\n",i+1);
print_array(array,size);
front=rear=0;
}
}


배열 출력 함수


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,1,83,202,55,4,119,81,15,47,19,28};
int size = sizeof(array)/sizeof(int);
printf("########### Sorting before ###########\n");
print_array(array, size);
radix_sort(array, size);
}


실행 결과




참고 : 위키백과(기수 정렬)




관련 포스팅


[DataStructure] 기수 정렬(Radix Sort)

[DataStructure] 퀵 정렬(Quick Sort)

[DataStructure] 셸 정렬(Shell Sort)

[DataStructure] 버블 정렬(Bubble Sort)

[DataStructure] 삽입 정렬(Insertion Sort)

[DataStructure] 선택 정렬(Selection Sort)



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

[C] 합병 정렬(Merge Sort)  (0) 2019.05.04
[C] 힙 정렬(Heap Sort)  (0) 2019.05.01
[C] 퀵 정렬(Quick Sort)  (0) 2019.04.24
[C] 셸 정렬(Shell Sort)  (2) 2019.04.23
[C] 버블 정렬(Bubble Sort)  (0) 2019.04.20

퀵 정렬(Quick Sort)




퀵정렬? 

퀵 정렬은 빠른 속도와, 간단한 구현방법 때문에

가장 많이 사용하는 정렬 방법으로 알려져 있습니다.


구현방법이 간편하다고 하지만, 개인적으로 이해하는데 시간이 좀 걸렸습니다.


퀵 정렬은 피벗으로 왼쪽에는 작은 값 오른쪽에는 큰값으로 정렬하는 방법입니다.


피벗?

특정 기준은 피벗(pivot)이라고 부릅니다.


복잡도

최악의 경우의 복잡도는 아래와 같지만 

(최악의 경우 : 피벗이 가장 작은 수 이거나 가장 큰 수가 계속 선정되는 경우)



평균적인 복잡도는 아래와 같습니다.



어떠한 방법?

피벗을 가장 마지막 인덱스로 설정했습니다.


아래와 같은 배열이 있을 때 



피벗 6을 기준으로 왼쪽과 오른쪽 끝에서부터


왼쪽은 6보다 큰 수 오른쪽은 6보다 작은 수를 찾습니다.



양쪽 다 찾은 수가 있다면 자리를 교환 해줍니다.



교환 후 계속해서 진행 한 후 


왼쪽과 오른쪽의 수가 같아 지면 종료하고 


피벗과 만난지점의 자리를 바꿔줍니다.



자리를 바꾼뒤 확인 해보면


피벗 기준으로 왼쪽에는 작은 수 오른쪽에는 큰수만 오게 됩니다.



각각 나눠진 영역에서 반복해서 같은 방법으로 진행 하면 정렬이 됩니다.


반복은 재귀호출로 진행하게 됩니다.



배열과 재귀호출을 이용한 퀵 정렬 예제


퀵 정렬 함수


if문 : 재귀 호출을 통해 종료를 위한 조건문


첫번째 while : 피벗보다 작은 수 큰 수를 찾기위한 반복문


두번째, 세번째 while : 각각 피벗보다 작은 수, 큰수를 찾는 반복문


첫번째 재귀 호출 : 피벗 기준 왼쪽을 정렬하기 위한 재귀 호출


두번째 재귀 호출 : 피벗 기준 오른쪽을 정렬하기 위한 재귀 호출


void quick_sort(int array[], int size){
int pivot, temp;
if(size>1){
pivot = array[size-1];
int left = -1;
int right = size-1;
while(1){
while(array[++left]<pivot);
while(array[--right]>pivot);
if(left>=right) break;
temp = array[left];
array[left] = array[right];
array[right] = temp;
}
temp = array[left];
array[left] = array[size-1];
array[size-1] = temp;
quick_sort(array, left);
quick_sort(array+left+1, size-left-1);
}
}


배열 출력 함수


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


실행 함수


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


void main(){
int array[] = {2,7,1,3,4,0,8,5,9,6};
int size = sizeof(array)/sizeof(int);
printf("########### Sorting before ###########\n");
print_array(array, size);
quick_sort(array, size);
printf("########### Sorting after ###########\n");
print_array(array, size);
}


실행 결과




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

위키백과(퀵 정렬)




관련 포스팅


[DataStructure] 기수 정렬(Radix Sort)

[DataStructure] 퀵 정렬(Quick Sort)

[DataStructure] 셸 정렬(Shell Sort)

[DataStructure] 버블 정렬(Bubble Sort)

[DataStructure] 삽입 정렬(Insertion Sort)

[DataStructure] 선택 정렬(Selection Sort)



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

[C] 힙 정렬(Heap Sort)  (0) 2019.05.01
[C] 기수 정렬(Radix Sort)  (1) 2019.04.30
[C] 셸 정렬(Shell Sort)  (2) 2019.04.23
[C] 버블 정렬(Bubble Sort)  (0) 2019.04.20
[C] 삽입 정렬(Insertion Sort)  (0) 2019.04.19

셸 정렬(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

버블 정렬(Bubble Sort)




버블 정렬 ? 

버블 정렬은 거품 정렬이라고도 불리는 정렬 입니다.


아래 그림과 같이 인접하는 두 항을 


전부 비교해서 정렬하는 방법입니다.



n개의 항이 있다면 n-1번씩 비교 하게 됩니다.


정렬 알고리즘 중에서 가장 비효율적인 방법이라고 합니다.



배열을 이용한 버블 정렬 예제


버블 정렬 함수


이전항(array[j-1]), 다음항(array[j])을 비교해서 

이전항이 클 경우 자리를 바꿔주고 그렇지 않으면 패스합니다.

void bubble_sort(int array[], int size){
int t;
for(int i=0; i<size-1; i++){
for(int j=1; j<size; j++){
if(array[j-1]>array[j]){
t = array[j-1];
array[j-1] = array[j];
array[j] = t;
}
}
}
}


실행 함수


정렬 전과 후 배열 출력


void main(){
int array[] = {11,10,33,22,55,9};
int size = sizeof(array)/sizeof(int);
printf("########### Sorting before ###########\n");
for(int i=0; i<size; i++){
printf("%-4d",array[i]);
}
bubble_sort(array,size);
printf("\n########### Sorting after ###########\n");
for(int i=0; i<size; i++){
printf("%-4d",array[i]);
}
}


실행 결과




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

위키백과(버블정렬)




관련포스


[DataStructure] 기수 정렬(Radix Sort)

[DataStructure] 퀵 정렬(Quick Sort)

[DataStructure] 셸 정렬(Shell Sort)

[DataStructure] 버블 정렬(Bubble Sort)

[DataStructure] 삽입 정렬(Insertion Sort)

[DataStructure] 선택 정렬(Selection Sort)



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

[C] 퀵 정렬(Quick Sort)  (0) 2019.04.24
[C] 셸 정렬(Shell Sort)  (2) 2019.04.23
[C] 삽입 정렬(Insertion Sort)  (0) 2019.04.19
[C] 선택 정렬(Selection Sort)  (0) 2019.04.19
[C] 트리(Tree)  (0) 2019.04.07

삽입 정렬(Insertion Sort)




삽입 정렬?

삽입 정렬은 이미정렬된 앞부분의 항들과 비교해서


사이에 작은 수를 삽입하여 정렬하는 방법입니다.


아래 위키백과의 애니메이션을 보면 쉽게 이해할 수 있습니다.


https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC


복잡도

삽입정렬의 복잡도는 아래와 같습니다.



배열을 이용한 삽입 정렬 예제


삽입 정렬 함수


기준항(temp)와 정렬된 앞 요소들의 크기를 비교하고 한칸 씩  뒤로 옮긴 후 기준항을 삽입합니다.


두 번째 항부터 비교를 시작하므로 i는 1부터 시작합니다.


void insertion_sort(int array[], int size){
int j,temp;
for(int i=1; i<size; i++){
j=i;
temp = array[i];
while(j>0 && array[j-1]>temp){
array[j] = array[j-1];
j--;
}
array[j] = temp;
}
}


실행 함수


정렬 전과 후 배열 출력


void main(){
int array[] = {11,10,33,22,55,9};
int size = sizeof(array)/sizeof(int);
printf("########### Sorting before ###########\n");
for(int i=0; i<size; i++){
printf("%-4d",array[i]);
}
insertion_sort(array,size);
printf("\n########### Sorting after ###########\n");
for(int i=0; i<size; i++){
printf("%-4d",array[i]);
}
}


실행 결과




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

위키백과(삽입정렬)




관련 포스팅


[DataStructure] 기수 정렬(Radix Sort)

[DataStructure] 퀵 정렬(Quick Sort)

[DataStructure] 셸 정렬(Shell Sort)

[DataStructure] 버블 정렬(Bubble Sort)

[DataStructure] 삽입 정렬(Insertion Sort)

[DataStructure] 선택 정렬(Selection Sort)




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

[C] 셸 정렬(Shell Sort)  (2) 2019.04.23
[C] 버블 정렬(Bubble Sort)  (0) 2019.04.20
[C] 선택 정렬(Selection Sort)  (0) 2019.04.19
[C] 트리(Tree)  (0) 2019.04.07
[C] 큐(Queue)  (2) 2019.04.01

선택 정렬(Selection Sort)




선택 정렬?

선택 정렬은 기준 항과 우측항 전체를 다 비교한 후 가장 작은수를 가장 앞으로 이동해서 정렬하는 방법입니다.


아래 위키백과의 애니메이션을 보면 쉽게 이해할 수 있습니다.


https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC


복잡도

선택정렬의 복잡도는 아래와 같습니다.




배열을 이용한 선택 정렬 예제


선택 정렬 함수


최소값(min)과 최소값의 인덱스(minIndex)를 구한 후 기준항(array[i])과 자리 교체


void selection_sort(int array[], int size){
int min, minIndex;
for(int i=0; i<size-1; i++){
int min = array[i];
int minIndex = i;
for(int j=i+1; j<size; j++){
if(min>array[j]){
min = array[j];
minIndex = j;
}
}
array[minIndex] = array[i];
array[i] = min;
}
}


실행 함수


정렬 전과 후 배열 출력


void main (){
int array[] = {11,10,33,22,55,9};
int size = sizeof(array)/sizeof(int);
printf("########### Sorting before ###########\n");
for(int i=0; i<size; i++){
printf("%-4d",array[i]);
}
printf("\n########### Sorting after ###########\n");
selection_sort(array, size);
for(int i=0; i<size; i++){
printf("%-4d",array[i]);
}
}


실행 결과





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

위키백과(선택정렬)



관련 포스팅


[DataStructure] 기수 정렬(Radix Sort)

[DataStructure] 퀵 정렬(Quick Sort)

[DataStructure] 셸 정렬(Shell Sort)

[DataStructure] 버블 정렬(Bubble Sort)

[DataStructure] 삽입 정렬(Insertion Sort)

[DataStructure] 선택 정렬(Selection Sort)




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

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

스택(Stack)



스택(Stack)?

스택은 LIFO(Last In First Out)구조로 


가장 나중에 들어간 값이 가장먼저 나오는 구조입니다.


삽입하는 PUSH와 삭제하는 POP 동작이 있습니다.


1. 스택 형태


2. PUSH


3. POP




배열을 이용한 예제


스택으로 사용할 int형 배열 선언 및 초기화 함수


#include "stdio.h"
#define MAX 10


int stack[MAX];
int top;


void init_stack(void){
top = -1;
}


스택에 push하는 함수


스택 크기보다 크면 오버플로우 발생


int push(int t){
if(top >=MAX-1){
printf("########### STACK OVER FLOW ###########\n");
return -1;
}else{
stack[++top] = t;
return t;
}
}


스택에서 pop하는 함수


스택 크기보다 작으면 오버플로우 발생


int pop(void){
if(top<0){
printf("########### STACK UNDER FLOW ###########\n");
return -1;
}
return stack[top--];
}

스택의 값을 출력하는 함수


void print_stack(void){
printf("PRINT STACK \n");
for(int i=top; i>=0; i--){
printf("%-6d",stack[i]);
}
printf("\n");
}

메인함수

11개의 값을 push할 경우 10개는 정상적으로 push 되지만,
나머지 1개의 값은 스택 오버플로우가 발생합니다.

두번째 pop을 수행할 때 5개의 값은 정상적으로 pop 되지만,
나머지 1개의 값은 스택 언더플로우가 발생합니다.

void main(){
init_stack();
printf("########### PUSH ###########\n");
for(int i=0; i<11; i++){
push(i);
}
print_stack();
printf("########### POP ###########\n");
for(int i=0; i<5; i++){
pop();
}
print_stack();
for(int i=0; i<6; i++){
pop();
}
}

실행 결과


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






'언어 > 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] 연결리스트(LinkedList)  (0) 2019.03.28

연결리스트(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