'알고리즘'에 해당되는 글 2건

  1. 2015.12.12 [S/W] 간단한 큐(Queue)의 구현
  2. 2015.06.04 Quick Sort (퀵정렬)
2015.12.12 10:03


간단한 큐(Queue)의 구현


순환 큐가 가장 좋은 것으로 알고 있지만 

빠른 알고리즘의 구현을 할 경우에는 전체 큐의 범위를 넉넉하게 잡고 아래와 같은 방식으로 구현하였다.

큐는 BFS 알고리즘을 쓸때 주로 이용된다.


여기서 사용된 Front 와 Rear 의 용도는 다음과 같다.

값의 존재 기준으로 보면
Front 는 값이 존재하는 제일 앞에서 index 값이 -1 만큼인 값
Rear 는 값이 존재하는 제일 마지막에서 index 값이 +1 만큼인 값

값을 넣어야 하는 기준으로 보면
값을 꺼낼 때 Front 의 현재 index 에서 +1의 위치 값을 꺼내온다.
값을 넣을 때 Rear 의 index 위치에 값을 넣는다.

Queue에 Push 할때는 Rear 가 가리키는 Index 에 넣고 Rear 의 값을 +1 한다.
Queue에 있는 값을 Pop으로 꺼낼때는 Front 의 +1한 다음 Index 값이 Rear 와 같은 경우 Null 을 알려주고 그렇지 않은 경우 Front 값을 +1 하고 해당 위치에 값을 Return 한다.


#include <stdio.h>

#define SIZE 100

struct vertex{
	int x;
	int y;
}typedef vertext;

vertext queue[SIZE];
int front=-1;
int rear=0;

void push_rear(vertext a){
	queue[rear++] = a;
}

vertext pop_rear(){
	if (rear == front+1){
		// QUEUE NULL
		printf("QUEUE is NULL\n");
	}
	else{
		return queue[++front];
	}
}

void printQueue(){
	int i=front+1;
	printf("QUEUE : ");
	if (i < rear){
		do{
			printf("(%d, %d) ", queue[i].x, queue[i].y);
			i++;
		} while (i< rear);
	}
	printf("\n");

}

int main(){
	int i=0;
	int T=0;
	vertext value;
	int b,c,d,e,f,g;

	int a[10];
	
	while (1){
		printf("----------------\n");
		printf("1. Push 2.Pop\n");
		scanf("%d", &T);

		if (T == 1){
			scanf("%d %d", &value.x, &value.y);
			printf("%d %d", value.x, value.y);
			push_rear(value);

		}
		else if (T == 2){
			pop_rear();
		}

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

	return 0;
}
 



신고


Posted by injunech
2015.06.04 17:38


Quick Sort(퀵정렬)

 

알고리즘

 

연속적인 분할에 의한 정렬처음 하나의 축을 정해서 이 축의 값보다 작은 값은 왼쪽에

큰 값은 오른쪽으로 위치시킨다왼쪽과 오른쪽의 수 들은 다시 각각의 축으로 나누어져

축값이 1이 될 때까지 정렬한다

 

특징

 

안정성 없음

 

O(NlogN) : 최선의 경우 log2N (축값이 정확히 가운데를 가질 경우)

O(N^2) : 최악의 경우

 

가장 많이 사용되는 정렬법으로 1960 C.A.R. Hoare에 의해 고안되었다.

 

Code(코드)

 

재귀함수를 사용한다.

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define SIZE 20
#define SWAP(x,y,t) ( (t)=(x), (x)=(y), (y)=(t) )
 
void QuickSort(int left, int right);
 
int array[SIZE];
 
int main(void){
int i;
srand((unsigned int)time(NULL));
 
for ( i = 0; i < SIZE; i++ )
array[i] = rand() % (SIZE*10) + 1;
 
printf("array for sorting : \n");
 
for ( i = 0; i < SIZE; i++ )
printf("%4d", array[i]);
 
 
printf("\nProcessing : \n");
 
QuickSort(-1, SIZE-1);
 
printf("Soredted array : \n");
 
for ( i = 0; i < SIZE; i++ )
printf("%4d", array[i]);
 
printf("\n");
 
return 0;
}
 
void QuickSort(int left, int right){
int m, p, t;
int i, j;
 
for ( i = 0; i < SIZE; i++ )
printf("%4d", array[i]);
 
printf("\n");
 
if ( left < right ){
p = array[right];
for(i=left-1, j=right; ; ){
while ( array[++i] < p );
while ( array[--j] > p );
 
if ( i > j )
break;
 
SWAP(array[i], array[j], t);
}
 
array[right] = array[i];
array[i] = p;
 
QuickSort(left, j);
QuickSort(i+1, right);
}
}


신고


Posted by injunech