#include<alloc.h>
#include<stdio.h>
#include<conio.h>
//=======================================
void taolap(int *A,int n)
  {
    int i;
    printf("\n Tao lap day so:\n");
    for(i=0;i<n;i++)
      {
	printf("\n A[%d]=",i);
	scanf("%d",&A[i]);
      }
  }
void dayso(int *A,int n)
  {
    int i;
    for(i=0;i<n;i++)
      printf("%5d",A[i]);
  }

void select(int *A,int n)
  {
    int i,j,temp;
    for(i=0;i<n-1;i++)
      {
	for(j=i+1;j<n;j++)
	  {
	    if(A[i]>A[j])
	      {
		temp=A[i];
		A[i]=A[j];
		A[j]=temp;
	      }
	  }
       }
    printf("\n Ket qua thu duoc la:");
    dayso(A,n);
  }
void luachon()
  {
    clrscr();
    int *A,n;
    printf("\n \t SAP XEP KIEU LUA CHON\n");
    printf("\n Nhap so phan tu n=");
    scanf("%d",&n);
    A=(int*)malloc(n*sizeof(int));
    taolap(A,n);
    select(A,n);
    free(A);
    getch();
  }

//=======================================
void in2(int *A,int n)
  {
    int i;
    for(i=0;i<n;i++)
    printf("%5d",A[i]);
  }
void tructiep()
  {
    clrscr();
    int *A,i,j,n,temp;
    printf("\n SAP XEP KIEU TRUC TIEP\n");
    printf("\n\t SAP XEP KIEU TRUC TIEP\n");
    printf("\n Nhap so phan tu n=");
    scanf("%d",&n);
    A=(int*)malloc(n*sizeof(int));
    printf("\n Tao lap day so:\n");
    for(i=0;i<n;i++)
      {
	printf("\n A[%d]=",i);
	scanf("%d",&A[i]);
      }
    for(i=1;i<n;i++)
      {
	temp=A[i];
	for(j=i-1;j>=0&&temp<A[j];j--)
	  A[j+1]=A[j];
	A[j+1]=temp;
	printf("\n\nKet qua lan thu %d:",i);
	in2(A,i+1);
      }
    free(A);
    getch();
  }
//=======================================
void tlap(int *A,int n)
  {

    int i;
    printf("\n");
    printf("\n Tao lap day so:\n");
    for(i=0;i<n;i++)
      {
	printf("\n A[%d]=",i);
	scanf("%d",&A[i]);
      }
  }
void in1(int *A,int n)
  {
    int i;
    for(i=0;i<n;i++)
    printf("%5d",A[i]);
  }

void bubble(int *A,int n)
  {
    int i,j,temp;
    for(i=1;i<n;i++)
      {
	for(j=n-1;j>=i;j--)
	  {
	    if(A[j-1]>A[j])
	      {
		temp=A[j-1];
		A[j-1]=A[j];
		A[j]=temp;
	      }
	  }
	printf("\n\n Ket qua lan %d:",i);
	in1(A,n);
      }
  }
void suibot()
  {
    clrscr();
    int *A,n;
    printf("\n SAP XEP KIEU SUI BOT\n");
    printf("\n Nhap so phan tu n=");
    scanf("%d",&n);
    A=(int*)malloc(n*sizeof(int));
    tlap(A,n);
    bubble(A,n) ;
    free(A);
    getch();
  }
//=======================================
void qs(int *A,int left,int right)
  {
    int i,j,x,y;
    i=left;
    j=right;
    x=A[(left+right)/2];
    do
      {
	while(A[i]<x&&i<right)i++;
	while(A[j]>x&&j>left)j--;
	if(i<=j)
	  {
	    y=A[i];
	    A[i]=A[j];
	    A[j]=y;
	    i++;
	    j--;
	  }
      }while(i<=j);
    if(left<j)qs(A,left,j);
    if(i<right)qs(A,i,right);
  }
void quick(int *A,int n)
  {
    qs(A,0,n-1);
  }

void in3(int *A,int n)
  {
    int i;
    for(i=0;i<n;i++)
      printf("%5d ",A[i]);
  }
void nhanh()
  {
    clrscr();
    int *A,n;
    printf("\n SAP XAP NHANH\n");
    printf("\n So phan tu n=");
    scanf("%d",&n);
    A=(int*)malloc(n*sizeof(int));
    printf("\n\n Tao lap day so:\n");
    for(int i=0;i<n;i++)
      {
	printf("\n A[%d]=",i);
	scanf("%d",&A[i]);
      }
    quick(A,n);
    printf("\n\n");
    printf("Ket qua thu duoc la:\n\n");
    in3(A,n);
    getch();
    free(A);
  }
//=======================================
void in4(int *A,int n)
  {
    for(int i=0;i<n;i++)
      printf("%5d",A[i]);
  }
void merge(int *A,int n)
  {
    int i,k,j,low1,up1,low2,up2,size;
    int *ds;
    size=1;
    ds=(int*)malloc(n*sizeof(int));
    while(size<n)
      {
	low1=0;
	k=0 ;
	while(low1+size<n)
	  {
	    low2=low1+size;
	    up1=low2-1;
	    if(low2+size-1<n)
	      up2=low2+size-1;
	    else
	      up2=n-1;
	    for(i=low1,j=low2;i<=up1 && j<=up2;k++)
	      {
		if(A[i]<=A[j])
		  ds[k]=A[i++];
		else
		  ds[k]=A[j++];
	      }
	    for(;i<up1;k++)
	      ds[k]=A[i++];
	    for(;j<up2;k++)
	      ds[k]=A[j++];
	    low1=up2+1;
	  }
	for(i=low1;k<n;i++)
	  ds[k++]=A[i];
	for(i=0;i<n;i++)
	  A[i]=ds[i];
	size*=2;
      }
    printf("\n \n Ket qua thu duoc la:\n\n");
    in4(A,n);
    free(ds);
  }
void hoanhap()
  {
    clrscr();
    int *A,n,i;
    printf("\n \t SAP XEP KIEU HOA NHAP\n");
    printf("\n So phan tu n=");
    scanf("%d",&n);
    A=(int*)malloc(n*sizeof(int));
    printf("\n Tao lap day so:\n");
    for(i=0;i<n;i++)
      {
	printf("\nA[%2d]=",i);
	scanf("%d",&A[i]);
      }
    merge(A,n);
    printf("\n");
    getch();
    free(A);
  }

//=======================================
void in5(int *A,int n)
  {
    for(int i=0;i<n;i++)
      printf("%5d",A[i]);
  }
void shaker(int *A,int n)
  {
    int i,j,temp,tdoi;
    do
      {
	tdoi=0;
	for(i=n-1;i>0;i--)
	  {
	    if(A[i-1]>A[i])
	      {
		temp=A[i-1];
		A[i-1]=A[i];
		A[i]=temp;
		tdoi=1;
	      }
	  }
	for(j=1;j<n;j++)
	  {
	    if(A[j-1]>A[j])
	      {
		temp=A[j-1];
		A[j-1]=A[j];
		A[j]=temp;
		tdoi=1;
	      }
	  }

      }while(tdoi);
    printf("\n\n Ket qua la :",tdoi);
    in5(A,n);
  }
void shaker()
  {
    clrscr();
    int *A,n,i;
    printf("\n \tSHAKER_SORT\n");
    printf("\n So phan tu n=");
    scanf("%d",&n);
    A=(int*)malloc(n*sizeof(int));
    printf("\n \n Tao lap day so:\n");
    for(i=0;i<n;i++)
      {
	printf("\n A[%2d]=",i);
	scanf("%d",&A[i]);
      }
    shaker(A,n);
    getch();
    free(A);
  }


//=======================================
void main()
  {
    while(1) {
    clrscr();
    int key;
    printf("\n\tSAP XEP VA TIM KIEM\n");
    printf("\n 1.Selection_sort\n");;
    printf("\n 2.Bubble_sort\n");
    printf("\n 3.Insertion_sort\n");
    printf("\n 4.Quick_sort\n");
    printf("\n 5.Merge_sort\n");
    printf("\n 6.Shaker_sort\n");
    printf("\n 0.Tro ve");
    printf("\nBam mot phim de chon chuc nang:");
    scanf("%d",&key);
    if(key==0) break;
   
    switch(key)
      {
	case 1:
	       clrscr();
	       luachon();
	       printf("\n\n\tAn phim bat ky de tro lai menu chinh");
	       getch();
	       clrscr();
	       break;
	case 2:
	       clrscr();
	       suibot();
	       printf("\n\n\tAn phim bat ky de tro lai menu chinh");
	       getch();
	       clrscr();
	       break;
	case 3:
	       clrscr();
	       tructiep();
	       printf("\n");
	       printf("\nAn phim bat ky de tro lai menu chinh");
	       getch();
	       clrscr();
	       break;
	case 4:
	       clrscr();
	       nhanh();
	       printf("\n");
	       printf("\nAn phim bat ky de tro lai menu chinh");
	       getch();
	       clrscr();
	       break;
	case 5:
	       clrscr();
	       hoanhap();
	       printf("\n");
	       printf("\nAn phim bat ky de tro lai menu chinh");
	       getch();
	       clrscr();
	       break;
	case 6:
	       clrscr();
	       shaker();
	       printf("\n");
	       printf("\nAn phim bat ky de tro lai menu chinh");
	       getch();
	       clrscr();
	       break;

      }
     }
   // getch();
  }

char *dnchuoi(char *s)
{
  char *tmp, i;

  i = 0;
  tmp = (char *)malloc(strlen(s)+1);
  while (i<strlen(s))
    *(tmp+i) = *(s + strlen(s) - i++ - 1);
    *(tmp+i) = 0;
  return tmp;
}

void main()
{
  char hello[] = "Hello World";
  char *s;

  printf("\nChuoi ban dau = %s", hello);
  s = dnchuoi(hello);
  printf("\nChuoi dao nguoc = %s", s);
  getch();
}