Segregate 0s and 1s in an array by looping only once

Segregate 0s and 1s in an array by looping only once

Segregate 0s and 1s in an array by looping only once  

In this tutorial we see how to segregate 0s and 1s in an array just by looping only once, ie. O(n). With simple logic we will me maintaining 2 pointers like i and j where i will be pointing 0th location and j will be pointing Nth location. Just we need to loop array and check if each index value and need to segregate accordingly. Lets see simple Java example to Segregate 0s and 1s in an array and an important by looping array only once.

public class SegregateArray {

 public static void main(String[] args) {

  int[] arr = new int[] { 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1 };

  for (int i = 0, j = arr.length - 1; i < j;) {
   if (arr[i] == 1) {

    if (arr[j] == 0) {
     arr[i] = 0;
     arr[j] = 1;
    }
    j--;
   } else {
    i++;
   }
  }

  for (int i = 0; i < arr.length; i++) {
   System.out.println(arr[i] + ", ");
  }
 }
}

OUTPUT:

0, 
0, 
0, 
0, 
0, 
0, 
0, 
1, 
1, 
1, 
1, 
1, 
1, 

Sorting Integer array without any sorting algorithm or loop ?

Sorting Integer array without any sorting algorithm or loop ?

Sorting Integer array without any sorting algorithm or loop  

In this tutorial we will see about how to sort and print the integer array without using any sorting algorithm or without using any loop to sort. Here it comes the Data Structure and we are going to use Binary Search Tree with In-order traversal. Just need to create BST with the given array and traverse through BST using In-order traversal. By this way we can sort given array without using any sorting algorithm or loop to sort the given array.

Lets see simple Java code how to create BST with the given integer array and to traverse through BST and print the given array in sorted order.

class BST {

 BST left; // Left subtree
 BST right; // Right subtree
 int data; // Element

 public BST(int data) {
  this.data = data;
 }
}


public class SortingWithoutLoop {

 public static void main(String[] args) {

  int val[] = new int[] { 5, 8, 3, 7, 0, 43, 65, 8, 2, 89, 25 };
  BST root = new BST(val[0]);
  for (int i = 1; i < val.length; i++) {
   BST lastNode = getLastNode(root, val[i]);
   if (val[i] > lastNode.data) {
    BST tmp = new BST(val[i]);
    lastNode.right = tmp;
   } else {
    BST tmp = new BST(val[i]);
    lastNode.left = tmp;
   }
  }
  
  inOrderTraversal(root);
 }

 public static BST getLastNode(BST root, int val) {

  if (root.right != null && val > root.data) {
   return getLastNode(root.right, val);
  } else if(root.left != null && val < root.data){
   return getLastNode(root.left, val);
  }
  return root;
 }

 public static void inOrderTraversal(BST root) {

  if (root.left != null) {
   inOrderTraversal(root.left);
  }

  System.out.print(root.data + ", ");

  if (root.right != null) {
   inOrderTraversal(root.right);
  }
 }
}

OUTPUT:

0, 2, 3, 5, 8, 8, 25, 43, 65, 89,