하얀나다의블로그

선택정렬, 버블정렬, 삽입정렬, 쉘정렬, 퀵정렬, 합병정렬(순환버전), 합병정렬(비순환버전), 힙정렬 C로 작성함

 

 

선택정렬

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

 

#define MAX_SIZE 10

 

void selection_sort(int*,int n);

void SWAP(int *, int *);

void OUTPUT(int*,int n );

 

int main(void)

{

int i, arr[MAX_SIZE] = {0};

// 임의의 난수로 배열 초기화

srand(time(NULL));

for(i = 0 ; i<MAX_SIZE; i++)

*(arr + i) = rand() % 9999 +0; // arr[i] = rand() % 99 + 1;

printf("정렬 전 : ");

OUTPUT(arr, MAX_SIZE);

selection_sort(arr,MAX_SIZE);

printf("정렬 후 : ");

OUTPUT(arr, MAX_SIZE);

return 0;

}

void selection_sort(int *p,int n)

{

int i, j, *pSm;

for(i=0; i<n-1; i++)

{

pSm = p+i; // pSm = &Arr[i]

for(j = i+1 ; j < n; j++)

if(*pSm > *(p+j))

pSm = p+j; // pSm = &Arr[j]

SWAP(p+i,pSm);

}

return;

}

void SWAP(int *pa, int *pb){

int temp;

temp = *pa;

*pa = *pb;

*pb = temp;

return;

}

void OUTPUT(int*p,int n){

int i;

for(i = 0; i<n; i++)

printf("%6d", *(p+i));

printf("\n");

return;

}

버블정렬

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

 

#define MAX_SIZE 10

#define TRUE 1

#define FALSE 0

 

void BUBBLE_sort(int*,int n);

void SWAP(int *, int *);

void OUTPUT(int*,int n );

 

int main(void)

{

int i, arr[MAX_SIZE] = {0};

 

// 임의의 난수로 배열 초기화

srand(time(NULL));

for(i = 0 ; i<MAX_SIZE; i++)

*(arr + i) = rand() % 9999 +0; // arr[i] = rand() % 99 + 1;

printf("정렬 전 : ");

OUTPUT(arr, MAX_SIZE);

BUBBLE_sort(arr,MAX_SIZE);

printf("정렬 후 : ");

OUTPUT(arr, MAX_SIZE);

return 0;

}

 

void BUBBLE_sort(int *p,int n)

{

int i, j,st;

st = FALSE;

 

while(!st){

st = TRUE;

for (i = 1; i<n;i++)

{

if(p[i-1]> p[i]){

SWAP(p+i-1,p+i);

st = FALSE;

}

}

}

void SWAP(int *pa, int *pb){

int temp;

temp = *pa;

*pa = *pb;

*pb = temp;

return;

}

void OUTPUT(int*p,int n){

int i;

for(i = 0; i<n; i++)

printf("%6d", *(p+i));

printf("\n");

return;

}

삽입정렬

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

 

#define MAX_SIZE 10

 

void Insertion_sort(int*,int n);

void OUTPUT(int*,int n );

 

int main(void)

{

int i, arr[MAX_SIZE] = {0};

// 임의의 난수로 배열 초기화

srand(time(NULL));

for(i = 0 ; i<MAX_SIZE; i++)

*(arr + i) = rand() % 9999 +0; // arr[i] = rand() % 9999 + 0;

 

printf("정렬 전 : "); OUTPUT(arr, MAX_SIZE);

Insertion_sort(arr,MAX_SIZE);

printf("정렬 후 : "); OUTPUT(arr, MAX_SIZE);

 

return 0;

}

void Insertion_sort(int *p,int n)

{

int i, j,temp;

for (i = 1 ; i < n; i ++)

{

temp = *(p+i);

//정렬된 지역에 temp가 들어갈 공간 확보!!!

for (j=i; *(p+j-1)>temp ; j--)

*(p+j) = *(p+j-1);

 

//확보된 공간에 temp를 저장

*(p+j) = temp;

}

}

return;

}

void OUTPUT(int*p,int n){

int i;

for(i = 0; i<n; i++)

printf("%6d", *(p+i));

printf("\n");

return;

}

쉘정렬

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

 

#define MAX_SIZE 10

 

void Shell_sort(int *p,int n);

void SWAP(int *, int *);

void OUTPUT(int*,int n );

 

int main(void)

{

int i, arr[MAX_SIZE] = {0};

 

// 임의의 난수로 배열 초기화

srand(time(NULL));

for(i = 0 ; i<MAX_SIZE; i++)

*(arr + i) = rand() % 9999 +0; // arr[i] = rand() % 99 + 1;

printf("정렬 전 : "); OUTPUT(arr, MAX_SIZE);

Shell_sort(arr,MAX_SIZE);

printf("정렬 후 : "); OUTPUT(arr, MAX_SIZE);

return 0;

}

void Shell_sort(int *p,int n){

int h,i,j,ss;

h =1;

do h = 3*h+1;

while(h<n);

do{

h = h/3;

for(i=h;i<n;i++){

ss = *(p+i);

j = i;

while(*(p+j-h)>ss){

 

*(p+j) = *(p+j-h);

j -= h;

if(j <= h-1) break;;

}

*(p+j) = ss;

}

}while(h>1);

}

void SWAP(int *pa, int *pb){

int temp;

temp = *pa;

*pa = *pb;

*pb = temp;

return;

}

void OUTPUT(int*p,int n){

int i;

for(i = 0; i<n; i++)

printf("%6d", *(p+i));

printf("\n");

return;

}

 

퀵정렬

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

 

#define MAX_SIZE 10

 

void Quick_Sort(int *arr, int *first, int *last);

int *Partition(int *arr, int *first, int *last);

void SWAP(int *, int *);

void OUTPUT(int*,int n );

 

 

int main(void)

{

int i, arr[MAX_SIZE] = {0};

 

// 임의의 난수로 배열 초기화

srand(time(NULL));

for(i = 0 ; i<MAX_SIZE; i++)

*(arr + i) = rand() % 9999 +0; // arr[i] = rand() % 99 + 1;

printf("정렬 전 : "); OUTPUT(arr, MAX_SIZE);

Quick_Sort(arr, arr, arr+MAX_SIZE);

printf("정렬 후 : "); OUTPUT(arr, MAX_SIZE);

return 0;

}

void Quick_Sort(int *arr, int *first, int *last)

{

int *mid = NULL;

if(first < last)

{

mid = Partition(arr, first, last);

Quick_Sort(arr, first, mid-1);

Quick_Sort(arr, mid+1, last);

}

return;

}

int *Partition(int *arr, int *first, int *last)

{

int *pi,*pj;

pj = first -1;

for(pi=first; pi<last; pi++)

if(*pi < *last)

SWAP(++pj,pi);

SWAP(pj+1,last);

return pj+1;

}

void SWAP(int *pa, int *pb){

int temp;

temp = *pa;

*pa = *pb;

*pb = temp;

return;

}

void OUTPUT(int*p,int n){

int i;

for(i = 0; i<n; i++)

printf("%6d", *(p+i));

printf("\n");

return;

}

합병정렬(순환버전)

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

 

#define MAX_SIZE 10

 

void Merge_Sort(int *arr, int *Low, int *High)

void Merge(int *arr, int *Low, int *mid, int *High)

void SWAP(int *, int *);

void OUTPUT(int*,int n );

 

int main(void)

{

 

int i, arr[MAX_SIZE] = {0};

 

// 임의의 난수로 배열 초기화

srand(time(NULL));

for(i = 0 ; i<MAX_SIZE; i++)

*(arr + i) = rand() % 9999 +0; // arr[i] = rand() % 99 + 1;

printf("정렬 전 : "); OUTPUT(arr, MAX_SIZE);

Merge_Sort(arr, arr, arr+MAX_SIZE-1);

printf("정렬 후 : "); OUTPUT(arr, MAX_SIZE);

return 0;

}

void Merge_Sort(int A[], int Low, int High)

{

int Mid = NULL;

if (Low < High) {

Mid = (Low + High)/2;

Merge_Sort (A, Low, Mid);

Merge_Sort (A, Mid+1, High);

Merge (A, Low, Mid, High);

}

}

void Merge (int A[], int Low, int Mid, int High)

{

int B[MAX_SIZE];

int i, LeftPtr, RightPtr, BufPtr;

LeftPtr = Low; RightPtr = Mid + 1; BufPtr = Low;

while (LeftPtr <= Mid && RightPtr <= High)

if (A[LeftPtr] < A[RightPtr])

B[BufPtr++] = A[LeftPtr++];

else B[BufPtr++] = A[RightPtr++];

if (LeftPtr > Mid)

for (i = RightPtr; i <=High; i++ )

B[BufPtr++] = A[i];

else

for (i = LeftPtr; i <= Mid; i++)

B[BufPtr++] = A[i];

for (i = Low; i <= High; i++)

A[i] = B[i];

}

void SWAP(int *pa, int *pb){

int temp;

temp = *pa;

*pa = *pb;

*pb = temp;

return;

}

void OUTPUT(int*p,int n){

int i;

for(i = 0; i<n; i++)

printf("%6d", *(p+i));

printf("\n");

return;

}

 

합병정렬(비순환버전)

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

 

#define MAX_SIZE 10

 

void Merge_Sort1(int A[], int Low, int High, int n)

void Merge1 (int A[], int Low, int Mid, int High)

void SWAP(int *, int *);

void OUTPUT(int*,int n );

int main(void)

{

int i, arr[MAX_SIZE] = {0};

 

// 임의의 난수로 배열 초기화

srand(time(NULL));

for(i = 0 ; i<MAX_SIZE; i++)

*(arr + i) = rand() % 9999 +0; // arr[i] = rand() % 99 + 1;

printf("정렬 전 : "); OUTPUT(arr, MAX_SIZE);

Merge_Sort1(arr, 0, MAX_SIZE-1, MAX_SIZE);

printf("정렬 후 : "); OUTPUT(arr, MAX_SIZE);

return 0;

}

void Merge_Sort1(int A[], int Low, int High, int n)

{

int i,Mid;

 

for (i=1; i< n-1; i = 2*i)

{

Low = 0;

while(Low <= n-1)

{

High = Low + 2*i -1;

if(High > n-1) High = n-1;

Mid = Low +i -1;

if(Mid <=n)

Merge1 (A, Low, Mid, High);

Low = High +1;

}

}

}

void Merge1 (int A[], int Low, int Mid, int High)

{

int B[MAX_SIZE];

int i, LeftPtr, RightPtr, BufPtr;

LeftPtr = Low; RightPtr = Mid + 1; BufPtr = Low;

while (LeftPtr <= Mid && RightPtr <= High)

if (A[LeftPtr] < A[RightPtr])

B[BufPtr++] = A[LeftPtr++];

else B[BufPtr++] = A[RightPtr++];

if (LeftPtr > Mid)

for (i = RightPtr; i <=High; i++ )

B[BufPtr++] = A[i];

else

for (i = LeftPtr; i <= Mid; i++)

B[BufPtr++] = A[i];

for (i = Low; i <= High; i++)

A[i] = B[i];

}

void SWAP(int *pa, int *pb){

int temp;

temp = *pa;

*pa = *pb;

*pb = temp;

return;

}

void OUTPUT(int*p,int n){

int i;

for(i = 0; i<n; i++)

printf("%6d", *(p+i));

printf("\n");

return;

}

 

 

힙정렬

 

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

 

#define MAX_SIZE 10

 

void Merge_Sort(int *arr, int *Low, int *High)

void Merge(int *arr, int *Low, int *mid, int *High)

void SWAP(int *, int *);

void OUTPUT(int*,int n );

 

int main(void)

{

int i, arr[MAX_SIZE] = {0};

 

// 임의의 난수로 배열 초기화

srand(time(NULL));

for(i = 0 ; i<MAX_SIZE; i++)

*(arr + i) = rand() % 9999 +0; // arr[i] = rand() % 99 + 1;

printf("정렬 전 : "); OUTPUT(arr, MAX_SIZE);

Heap_Sort(arr,MAX_SIZE);

printf("정렬 후 : "); OUTPUT(arr, MAX_SIZE);

return 0;

}

void Heap_Sort(int *p,int n)

{

int i;

 

for(i=n/2; i>0; i--)

MakeHeap(p,i-1,n-1);

for(i=n-1;i>0;i--){

SWAP(p+0,p+i);

MakeHeap(p,0,i-1);

}

}

void MakeHeap(int*p ,int Root, int LastNode)

{

int Parent, LeftSon, RightSon, Son, RootValue;

Parent = Root;

RootValue = p[Root];

LeftSon = 2 * Parent + 1;

RightSon = LeftSon + 1;

while (LeftSon <= LastNode) {

if (RightSon <= LastNode && p[LeftSon] < p[RightSon])

Son = RightSon;

else Son = LeftSon;

if (RootValue < p[Son]){

p[Parent] = p[Son];

Parent = Son;

LeftSon = Parent * 2 + 1;

RightSon = LeftSon + 1;

}

else break;

}

p[Parent] = RootValue;

}

 

void SWAP(int *pa, int *pb){

int temp;

temp = *pa;

*pa = *pb;

*pb = temp;

return;

}

void OUTPUT(int*p,int n){

int i;

for(i = 0; i<n; i++)

printf("%6d", *(p+i));

printf("\n");

return;

}