// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
#include<iostream.h>
#include<alloc.h>
#include<conio.h>
#include<iomanip.h>
#include<stdio.h>
#include<stdlib.h>
// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
#define thoat 0
// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
typedef int elem;
typedef struct
node
{
elem data;
struct node *next;
} nt;
typedef nt *pt;
// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
pt create();
int alloc(pt &tam);
int empty(pt list);
void nhapds(pt & ,pt &);
int insertlast(pt &list, pt &last, elem item);
int xuat(pt list);
int hoanvi(elem &a , elem &b);
int sap_xep(pt list);
int Chon(pt list);
void Quicksort(pt &list,pt &last);
// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
void main()
{
pt list, last,pred;
elem item;
clrscr();
cout<<"\n nhap ds thu 1:\n";
nhapds(list,last);
cout<<"\n danh sach ban dau la : ";
xuat(list);
// cout<<"\n";
// cout<<"\n danh sach sap xep doi cho la : ";
// sap_xep( list);
// xuat(list);
// cout<<"\n";
// cout<<"\n danh sach sap xep chon la : ";
// Chon( list);
// xuat(list);
cout<<"\n";
cout<<"\n danh sach sap xep Quicksort la : ";
Quicksort(list,last);
xuat(list);
getch();
}
// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
// ------------------------------------------------------------------------
pt create()
{
pt list;
if(!alloc(list))
return((pt)NULL);
list->next=(pt)NULL;
return(list);
}
// ------------------------------------------------------------------------
int alloc(pt &tam)
{
if((tam= new nt) == NULL)
return 0;
return 1;
}
// ------------------------------------------------------------------------
int empty(pt list)
{
return(list==NULL);
}
// ------------------------------------------------------------------------
void nhapds(pt &list,pt &last)
{
elem item;
list=last=create();
cout<<" nhap vao cac gia tri nguyen duong an 0 de thoat: ";
do
{
cin>>item;
if(item!=thoat)
// insertlast(list,item,last);
insertlast(list,last,item);
}
while(item!=thoat);
}
// ------------------------------------------------------------------------
int insertlast(pt &list, pt &last, elem item)
{
pt temp;
if(! alloc(temp))
return 0;
temp -> data = item;
temp -> next = NULL;
if(!empty(list))
last ->next = temp;
else
list = temp;
last = temp;
return 1 ;
}
// ------------------------------------------------------------------------
int xuat(pt list)
{
pt tam;
// tam = list->next;
tam = list;
while(tam!=NULL)
{
cout<<tam->data<<setw(5);
tam=tam->next;
}
return 1;
}
// ------------------------------------------------------------------------
int hoanvi(elem &a,elem &b)
{
elem t;
t = a;
a = b;
b = t;
return 1 ;
}
// ------------------------------------------------------------------------
int sap_xep(pt list)
{
pt tam,temp;
tam = list->next;
while(tam!=NULL)
{
temp =tam->next;
while(temp!=NULL)
{
if(temp->data < tam->data)
hoanvi(temp->data,tam->data);
temp = temp->next;
}
tam = tam->next;
}
return 1;
}
// ------------------------------------------------------------------------
int Chon(pt list)
{
pt tam,temp1,temp2;
tam = list->next;
while(tam!=NULL)
{
temp1 = tam ;
temp2 = tam->next;
while(temp2!=NULL)
{
if(temp1->data > temp2->data)
temp1 = temp2;
temp2 = temp2->next;
}
hoanvi(tam->data,temp1->data);
tam = tam->next;
}
return 1;
}
// ------------------------------------------------------------------------
void Quicksort(pt &list,pt &last)
{
pt temp,x,list1,list2,last1,last2;
if(list==NULL)
return ;
list1 = list2 = last1 = last2 = NULL;
x = last;
list = list->next;
while(list->next!=NULL)
{
temp = list;
list = list->next;
temp->next= NULL;
// cout<<"Ngoai if : "<<temp->data<<" x = "<<x->data<<"\n";getch();
if(temp->data <= x->data)
{
insertlast(list1,last1,temp->data);
cout<<"if : "<<temp->data<<" x = "<<x->data<<"\n";getch();
}
else
{
insertlast(list2,last2,temp->data);
cout<<"else : "<<temp->data<<" x = "<<x->data<<"\n";getch();
}
}
if(list1)
list->next =list1->next;
// last1->next= x;
else
{
list->next = x;
x->next=list2->next;
}
if(list2)
list->next = list2->next;
else
last = x;
cout<<endl;
cout<<"List1 = ";
xuat(list1);
getch();
cout<<endl;
cout<<"List2 = ";
xuat(list2);
getch();
cout<<endl;
cout<<"List = ";
xuat(list);
getch();
cout<<endl;
cout<<"Phan hoach xong ";getch();
// Quicksort(list1,last1);
// Quicksort(list2,last2);
// cout<<"x = "<<x->data<<endl;getch();
}
// -----------------------------------END----------------------------------
