#include <stdio.h>
#include <stdlib.h>
/*#include "Profiler.h"
#define MAX_SIZE 10000
#define STEP_SIZE 10
#define NUM_TEST 10
Profiler p("Traversal");
enum Traversal{Post,Pre,In};
typedef struct Node{
int key;
struct Node *right;
struct Node *left;
struct Node *parent;
};
int op;
void PrettyPrint(Node *node,int space){
if(NULL!=node){
for(int i=0;i<space;i++)
printf(" ");
printf("%d\n",node->key);
PrettyPrint(node->left,space+1);
PrettyPrint(node->right,space+1);
}
}
void IterativeTraversal(Node **root,Traversal traversal){
int direction=1;
Node *node=(*root);
do{
if(direction==1){
if(traversal==Pre){
op+=1;
printf("%d ",node->key);
}
if(NULL!=node->left)
node=node->left;
else direction=2;
}
if(direction==2){
if(traversal==In){
op+=1;
printf("%d ",node->key);
}
if(NULL!=node->right) {
node = node->right;
direction=1;
}
else direction=3;
}
if(direction==3){
if(traversal==Post){
op+=1;
printf("%d ",node->key);
}
if(NULL!=node->parent){
if(node==node->parent->left)
direction=2;
node=node->parent;
}
}
}
while((*root)!=node || direction!=3);
if(traversal==Post){
op+=1;
printf("%d ",node->key);
}
}
void PreorderTraversal(Node *node){
if(NULL==node)
return;
op+=1;
printf("%d ",node->key);
PreorderTraversal(node->left);
PreorderTraversal(node->right);
}
void PostorderTraversal(Node *node){
if(NULL==node)
return;
PostorderTraversal(node->left);
PostorderTraversal(node->right);
printf("%d ",node->key);
op+=1;
}
void InorderTraversal(Node *node){
if(NULL==node)
return;
InorderTraversal(node->left);
op+=1;
printf("%d ",node->key);
InorderTraversal(node->right);
}
void InsertInTree(Node **root, int key){
if(NULL==(*root)){
Node *temp = (Node *) malloc(sizeof(Node));
temp->parent=NULL;
temp->right=NULL;
temp->left=NULL;
temp->key=key;
(*root)=temp;
return;
}
Node *curr_node=(*root);
int ok=false;
while(!ok){
if(key>curr_node->key) {
if (NULL == curr_node->right) {
Node *temp = (Node *) malloc(sizeof(Node));
temp->parent=curr_node;
temp->right=NULL;
temp->left=NULL;
temp->key=key;
curr_node->right=temp;
curr_node=curr_node->right;
ok= true;
}
else curr_node=curr_node->right;
}
else if(key<curr_node->key){
if (NULL == curr_node->left) {
Node *temp = (Node *) malloc(sizeof(Node));
temp->parent=curr_node;
temp->right=NULL;
temp->left=NULL;
temp->key=key;
curr_node->left=temp;
curr_node=curr_node->left;
ok= true;
}
else curr_node=curr_node->left;
}
}
}
Node *GetMinimum(Node *root){
while(root->left!=NULL)
root=root->left;
return root;
}
Node *DeleteInTree(Node *node,int key){
if(node==NULL)
return node;
if(key>node->key){
node->right= DeleteInTree(node->right,key);
}
else if(key<node->key){
node->left= DeleteInTree(node->left,key);
}
else{
if(NULL==node->left && NULL==node->right){
free(node);
node=NULL;
}
else if(NULL==node->left){
Node *temp=node;
node=node->right;
free(temp);
temp=NULL;
}
else if(NULL==node->right){
Node *temp=node;
node=node->left;
free(temp);
temp=NULL;
}
else{
Node *temp= GetMinimum(node->right);
node->key=temp->key;
node->right= DeleteInTree(node->right,temp->key);
}
}
return node;
}
void Analysis(){
int arr[MAX_SIZE];
Node *root=NULL;
for(int n=STEP_SIZE;n<=MAX_SIZE;n+=STEP_SIZE){
Operation IterativePre=p.createOperation("Iterative Preorder",n);
Operation IterativePost=p.createOperation("Iterative Postorder",n);
Operation IterativeIn=p.createOperation("Iterative Inorder",n);
Operation RecursivePre=p.createOperation("Recursive Preorder",n);
Operation RecursivePost=p.createOperation("Recursive Postorder",n);
Operation RecursiveIn=p.createOperation("Recursive Inorder",n);
for(int test=0;test<NUM_TEST;test++){
FillRandomArray(arr,n,10,50000,true,UNSORTED);
for(int i=0;i<n;i++)
InsertInTree(&root,arr[i]);
op=0;
IterativeTraversal(&root,Pre);
IterativePre.count(op);
op=0;
IterativeTraversal(&root,Post);
IterativePost.count(op);
op=0;
IterativeTraversal(&root,In);
IterativeIn.count(op);
op=0;
PreorderTraversal(root);
RecursivePre.count(op);
op=0;
PostorderTraversal(root);
RecursivePost.count(op);
op=0;
InorderTraversal(root);
RecursiveIn.count(op);
for(int i=0;i<n;i++)
root= DeleteInTree(root,arr[i]);
}
}
p.divideValues("Iterative Preorder",NUM_TEST);
p.divideValues("Iterative Postorder",NUM_TEST);
p.divideValues("Iterative Inorder",NUM_TEST);
p.divideValues("Recursive Preorder",NUM_TEST);
p.divideValues("Recursive Postorder",NUM_TEST);
p.divideValues("Recursive Inorder",NUM_TEST);
p.showReport();
}
void Demo(){
int arr[13];
FillRandomArray(arr,13,10,45,true,UNSORTED);
Node *root=NULL;
for(int i=0;i<13;i++)
InsertInTree(&root,arr[i]);
printf("\n---Pretty Print---\n");
PrettyPrint(root,0);
printf("\n--Recursive Preorder---\n");
PreorderTraversal(root);
printf("\n--Recursive Postorder---\n");
PostorderTraversal(root);
printf("\n--Recursive Inorder---\n");
InorderTraversal(root);
printf("\n--Iterative Preorder---\n");
IterativeTraversal(&root,Pre);
printf("\n--Iterative Postorder---\n");
IterativeTraversal(&root,Post);
printf("\n--Iterative Inorder---\n");
IterativeTraversal(&root,In);
}*/
int Partition(int *arr,int low,int high){
int aux,auxlow=low;
int pivot=arr[low];
while(low<=high){
while(arr[low]<=pivot)
low++;
while(arr[high]>pivot)
high--;
if(low<high){
aux=arr[low];
arr[low]=arr[high];
arr[high]=aux;
low++;
high--;
}
}
aux=arr[high];
arr[high]=pivot;
arr[auxlow]=aux;
return high;
}
void QuickSort(int *arr,int low,int high){
if(low<high){
int p= Partition(arr,low,high);
QuickSort(arr,low,p-1);
QuickSort(arr,p+1,high);
}
}
void HybridQuickSort(){
}
/*void DemoQuickSort(){
int arr[23];
FillRandomArray(arr,23,10,50,false,UNSORTED);
for(int i=0;i<23;i++)
printf("%d ",arr[i]);
printf("\n");
QuickSort(arr,0,22);
for(int i=0;i<23;i++)
printf("%d ",arr[i]);
}*/
int main() {
//Analysis();
// Demo();
freopen("algsort.in","r",stdin);
freopen("algsort.out","w",stdout);
int n;
scanf("%d",&n);
int *arr=(int *)malloc(sizeof(int)*n);
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
QuickSort(arr,0,n-1);
for(int i=0;i<n;i++)
printf("%d ",arr[i]);
free(arr);
//DemoQuickSort();
return 0;
}