def ShellSort(ary):
    length = len(ary)
    gap = round(length)
    step = length//2
    while step:
        for i in range(step,length,step):
            tmp = ary[i]
            for j in range(i,0,-step):
                if ary[j-step] > tmp:
                    ary[j] = ary[j-step]
                else:
                    break
            ary[j] = tmp
        if step == 1:
            break
        step = step//2
      
        
ary = [1,23,4,53,55,34,3,99,14]
ShellSort(ary)
print(ary)

#include <stdio.h>

struct _Node{
  int value;
  struct _Node *left;
  struct _Node *right;
  int height;
};

typedef struct _Node Node;

int max( int a, int b )
{
    return(a>b?a:b);
}

int Height( Node* tree )
{
    if( NULL == tree ) {
        return -1;
    }
    
    return tree->height;
}

int InitTree( Node* tree, int value )
{
  if( tree == NULL ) {
      return -1;
  }
  tree->value = value;
  tree->left = NULL;
  tree->right = NULL;
  tree->height = 0;
  return 0;
}

Node* SingleRotateWithLeft( Node* k1 )
{
    Node* k2;
    
    k2 = k1->left;
    k1->left = k2->right;
    k2->right = k1;
    
    k1->height = max(Height(k1->left), Height(k1->right)) + 1;
    k2->height = max( Height(k2->left), Height(k1) ) + 1;
    return k2;
}

Node* InsertTree(Node *tree, Node *new_node )
{
  if( new_node->value > tree->value ) {
    if( tree->right == NULL ) {
        tree->right = new_node;
    } else {
        InsertTree( tree->right, new_node );
    } 
  } else {
    if( tree->left == NULL ) {
        tree->left = new_node;
    } else {
        InsertTree( tree->left, new_node );
        if( Height(tree->left) - Height(tree->right) == 2 ) {
            if( new_node->value < tree->left->value ) {
                tree = SingleRotateWithLeft(tree);
            }
        }
    }
  }
  tree->height = max(Height(tree->left),Height(tree->right)) + 1;
  return tree;
}

void OrderTraverse( Node* tree )
{
  if( tree != NULL ) {
      printf("value:%d height:%d\t\n", tree->value,tree->height);
      OrderTraverse( tree->left );
      OrderTraverse( tree->right );
  }
}

int main()
{
  Node *tree = NULL;
  tree = (Node*)malloc(sizeof(Node));
  InitTree(tree, 5);
  int i = 0;
  int array[10] = {4,1};
  
  for( i = 0; i < 2; i++ ) {
      Node *node = NULL;
      node = (Node*)malloc(sizeof(Node));
      if( NULL == node ) {
        continue;
      }
      InitTree(node,array[i]);
      tree = InsertTree(tree,node);
  }
  printf("preOrderTraverse:\n");
  OrderTraverse(tree);
  printf("succeed!\n");
  return 0;
}

#include <stdio.h>

struct _Node{
  int value;
  struct _Node *left;
  struct _Node *right;
};

typedef struct _Node Node;

int InitTree( Node* tree, int value )
{
  if( tree == NULL ) {
      return -1;
  }
  tree->value = value;
  tree->left = NULL;
  tree->right = NULL;
}

int InsertTree(Node *tree, Node *new_node )
{
  if( new_node->value > tree->value ) {
    if( tree->right == NULL ) {
        tree->right = new_node;
    } else {
        InsertTree( tree->right, new_node );
    } 
  } else {
    if( tree->left == NULL ) {
        tree->left = new_node;
    } else {
        InsertTree( tree->left, new_node );
    }
  }
}

void OrderTraverse( Node* tree )
{
  if( tree != NULL ) {
      printf("%d ", tree->value);
      OrderTraverse( tree->left );
      OrderTraverse( tree->right );
  }
}

int main()
{
  Node *tree = NULL;
  tree = (Node*)malloc(sizeof(Node));
  InitTree(tree, 4);
  int i = 0;
  int array[10] = {4,1,6,9,7,8,3,2,5};
  
  for( i = 0; i < 9; i++ ) {
      Node *node = NULL;
      node = (Node*)malloc(sizeof(Node));
      if( NULL == node ) {
        continue;
      }
      InitTree(node,array[i]);
      InsertTree(tree,node);
  }
  
  OrderTraverse(tree);
  printf("succeed!\n");
  return 0;
}