#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#define MAX_SIZE 50

#define SWAP(x,y,t)((t)=(x),(x)=(y),(y)=(t))

void init(int list[]); //초기화 함수

int select_pivot(int list[],int left,int right); //left,right,중앙값 중에 중간 값을 pivot으로 선택하는 함수

int partition(int list[],int left,int right);

void quick_sort(int list[],int left,int right);

int main(void){

int n=MAX_SIZE;

int list[MAX_SIZE];

srand((int)time(NULL)); //난수 설정

init(list); //list 초기화

quick_sort(list,0,n-1);

}

void init(int list[]){

int i;

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

list[i]=rand()%100; //list를 두 자리 숫자로 초기화한다

}

}

int select_pivot(int list[],int left,int right){ //left, center, right 중에서 중간 값을 피벗으로 리턴한다

int num[3]={list[left],list[(left+right)/2],list[right]};

int mid,temp;

printf("left : %d\ncenter : %d\nright : %d\n",left,(left+right)/2,right); //leff, center, right의 위치출력

if((num[1]<=num[0] && num[0]<=num[2]) || (num[2]<=num[0] && num[0]<=num[1])){ //left가 중간값 일 경우

mid=num[0];

}

else if((num[0]<=num[1] && num[1]<=num[2]) || (num[2]<=num[1] && num[1]<=num[0])){ //center가 중간값 일 경우

mid=num[1];

SWAP(list[left],list[(left+right)/2],temp);

}

else if((num[0]<=num[2] && num[2]<=num[1]) || (num[1]<=num[2] && num[2]<=num[0])){ //right가 중간값 일 경우

mid=num[2];

SWAP(list[left],list[right],temp);

}

return mid; //중간 값을 리턴한다

}

int partition(int list[],int left,int right){

int pivot,temp;

int low,high;

low = left;

high = right+1;

if((right-left)>5){ //데이터가 5개 초과 일때, 3개 값중에 중간값을 피벗으로 한다

printf("-------------------------------------------------------------------------------\n");

pivot = select_pivot(list,left,right);

}

else{ //데이터가 5개 이하 일 때, 맨 왼쪽값을 피벗으로 한다

printf("-------------------------------------------------------------------------------\n");

pivot=list[left];

}

printf("pivot : %d\n",pivot);

do{

do //low를 1씩 증가

low++;

while(low<=right && list[low]<pivot); //low는 피봇보다 작으면 통과, 크면 정지

do

high--; //high를 1씩 감소

while(high>=left && list[high]>pivot); //high는 피봇보다 크면 통과, 작으면 정지

if(low<high) SWAP(list[low],list[high],temp); //정지된 위치의 숫자를 교환

}while(low<high); //low와 high가 교차하면 종료

SWAP(list[left],list[high],temp); //피벗을 중간위치로 이동

return high;

}

void quick_sort(int list[],int left,int right){

int i,q;

if(left<right){

q = partition(list,left,right); //q는 위치를 나타내는 index

for(i=0;i<MAX_SIZE;i++){ //list 출력

printf("%3d ",list[i]);

if(i%MAX_SIZE==MAX_SIZE-1)

printf("\n");

}

quick_sort(list,left,q-1); //피벗을 중심으로 왼쪽 부분

quick_sort(list,q+1,right); //피벗을 중심으로 오른쪽 부분

}

}

/* 주어진 그래프에서 출발할 정점을 입력 받는다. 그 정점으로부터 다른 정점까지의 최단거리와, 경로를 출력한다.*/

#include <stdio.h>

#define INT_MAX 2147483647 // 최대 정수

#define TRUE 1

#define FALSE 0

#define MAX_VERTICES 7 //정점의 수

#define INF 1000 //무한대(연결이 없는 경우)

int weight[MAX_VERTICES][MAX_VERTICES]={ //네트워크의 인접 행렬

{ 0, 7,INF,INF, 3, 10,INF},

{ 7, 0, 4, 10, 2, 6,INF},

{INF, 4, 0, 2,INF,INF,INF},

{INF, 10, 2, 0, 11, 9, 4},

{ 3, 2,INF, 11, 0,INF, 5},

{ 10, 6,INF, 9,INF, 0,INF},

{INF,INF,INF, 4, 5,INF, 0}};

int distance[MAX_VERTICES]; //시작 정점으로부터의 최단 경로 거리

int found[MAX_VERTICES]; //방문한 정점 표시

int path[MAX_VERTICES][MAX_VERTICES]; //최단거리 정점까지 거치는 노드들을 저장

int check[MAX_VERTICES];//한 정점으로 가는 정점을 표시

void path_init(int path[][MAX_VERTICES]); //path 인접행렬 초기화

int choose(int distance[],int n,int found[]); // 최단거리에 있는 정점을 찾는 함수

void shortest_path(int start, int n);//최단 경로 알고리즘

void main(){

int i,j;

int start;

path_init(path);

printf("시작 정점을 선택하시오 : ");

scanf("%d",&start);

printf("\n");

shortest_path(start,MAX_VERTICES);

for(i=0; i<MAX_VERTICES; i++){ //저장된 경로들 출력

printf("%d에서 %d까지의 최단거리 : %d \n",start,i,distance[i]);

printf("%d에서 %d까지의 노 드 : ",start,i);

for(j=0; j<MAX_VERTICES; j++){

if(path[i][j]!=INF){

printf("%d->", path[i][j]);//저장된 경로를 출력한다

}

}

printf("%d\n",i);

}

}

//path 인접행렬 초기화

void path_init(int path[][MAX_VERTICES]){

int i,j;

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

for(j=0;j<MAX_VERTICES;j++)

path[i][j] = INF;

}

// 최단거리에 있는 정점을 찾는 함수

int choose(int distance[],int n,int found[]){

int i,min,minpos;

min = INT_MAX;

minpos = -1;

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

if(distance[i]<min && !found[i]){

min = distance[i];

minpos = i;

}

return minpos;

}

//최단 경로 알고리즘

void shortest_path(int start, int n)

{

int i,j,u,w;

for(i=0; i<n; i++){//초기화

distance[i] = weight[start][i];

found[i] = FALSE;

check[i]=1;

path[i][0] = start;

}

found[start] =TRUE;//시작 정점 방문 표시

distance[start] = 0;

for(i=0; i<n-2; i++){

u = choose(distance, n, found);

found[u] = TRUE;

for(w=0; w<n;w++){

if(!found[w]){

if(distance[u]+weight[u][w] < distance[w]){

if(i==0){//처음에는 인접한 정점에 연결

path[w][check[w]] = u; //갱신된 경로를 경로 배열에 저장

check[w]++;

}

else{

for(j=0; j<(check[u]+1); j++){//저장된 만큼 반복

path[w][j] = path[u][j]; //경로를 갱신

path[w][j+1] = u; //끝부분에 자기자신을 저장

check[w]++;

}

}

distance[w] = distance[u] + weight[u][w];

}

}

}

}

}

프로그램을 짜다 보면, 간혹 내가 무언가를 창조하는 '마법사'가 되는 듯한 착각을 합니다. 그러나 요즘에 느끼는 것은 프로그램 내에서 인생에 대해서도 조금 깨달음을 얻곤 합니다. 

이번에 자료구조 과제는 '퀵정렬'을 코드로 짜보는 것이었습니다.

짜면서 느끼는 것은 

'도대체 임시로 피벗을 하나 잡아서, 값을 비교하여, 피벗보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로... 그리고 이런 과정을 피벗의 오른쪽 리스트와 왼쪽 리스트가 반복... 이런 복잡한 과정으로 꼭 정렬해야 하는가? 자료 중에 가장 작은 값을 찾아 맨 왼쪽부터 정렬하면 그게 가장 간단하게 생각할 수 있고 가장 간단한 방법이 아닌가?'

하지만 놀랍게도 복잡하다고 생각한 방법이 더 빠르게 자료를 처리했습니다. 앞으로 어떤 일을 하든지 

'어떻게하면 더욱 효율적으로 일을 처리할 수 있을까?'

라는 생각을 해봐야겠습니다... 무조건 간단해 보이는 것이 최선의 방법이 아니라는 걸 깨닫는 좋은 경험.

C언어를 쉽게 설명하는 블로그입니다!!! C언어를 배우시는 분들에게 도움이 될 듯!!!

http://itguru.tistory.com/notice/15