/*
재귀함수 - 퀵정렬
#include <stdio.h>
int a[10001];
int n;
void q_s(int s,int e)
{
int pivot=s;
int low=s,high=e+1,temp;
if(s>=e) return ;
do
{
do
{
low++;
}while(a[pivot]>a[low]);
do
{
high--;
}while(a[pivot]<a[high]);
if(low<high)
{
temp=a[high];
a[high]=a[low];
a[low]=temp;
}
}while(low<high);
temp=a[high];
a[high]=a[pivot];
a[pivot]=temp;
q_s(s,high-1);
q_s(high+1,e);
}
int main()
{
int i;
scanf("%d", &n);
for (i=1; i<=n; i++)
scanf("%d", &a[i]);
q_s(1,n);
for(i=1;i<=n;i++)
printf("%d ",a[i]);
return 0;
}
#include <stdio.h> #include <stdio.h>
int a[10001];
int n;
void q_s(int s,int e)
{
int pivot=s;
int low=s,high=e+1,temp;
if(s>=e) return ;
do
{
do
{
low++;
}while(a[pivot]>a[low]);
do
{
high--;
}while(a[pivot]<a[high]);
if(low<high)
{
temp=a[high];
a[high]=a[low];
a[low]=temp;
}
}while(low<high);
temp=a[high];
a[high]=a[pivot];
a[pivot]=temp;
q_s(s,high-1);
q_s(high+1,e);
}
int main()
{
int i;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
q_s(1,n);
for(i=1;i<=n;i++)
printf("%d\n",a[i]);
return 0;
}
재귀함수의 활용 2. 이분탐색
이분탐색 vs 순차탐색
binary search
#include<stdio.h>
int a[1001];
int n;
int b_s(int s,int e,int k) // a[s]부터 a[e]까지에서 k값의 위치 찾아라 .
{
int mid=(s+e)/2;
if(s>e) return -1;
if(a[mid]==k)
{
return mid;
}
else if(a[mid]>k)
{
b_s(s,mid-1,k);
}
else
{
b_s(mid+1,e,k);
}
}
int main()
{
int k,i;
scanf("%d %d",&n,&k);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("%d번째에 %d값이 있습니다.",b_s(1,n,k),k);
}
*/
#include <stdio.h>
int a[50001],o[50001];
int n;
int q_s(int s,int e)
{
int p;
int l=s,h=e+1,temp;
if(s>=e) return;
do
{
do
{
l++;
}while(a[p]>a[l]);
do
{
h--;
}while(a[p]<a[h]);
if(l<h)
{
temp=a[h];
a[h]=a[l];
a[l]=temp;
}
}while(l<h);
temp=a[h];
a[h]=a[p];
a[p]=temp;
q_s(s,h-1);
q_s(h+1,e);
}
int main()
{
int i;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
q_s(1,n);
for(i=1;i<=n;i++)
{
printf("%d",a[i]);
}
}
/*
#include<stdio.h>
int main()
{
int a[50001],s[50001],i,j,n,temp,cnt=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
s[i]=a[i];
}
q_b(1,n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(s[i]==a[j])
{
printf("%d ",j-1);
break;
}
}
}
return 0;
}
*/