Iterative Quick Sort in Java

Problem: - Quick Sort using Iterative approach.

Sample code for iterative quick sort:

import java.util.Stack;


public class HeapSortIterative {

 static int[] input2 = { 2, 23, 45, 67, 5, 27, 6, 7, 12, 21, 67, 89 };
 static int[] input3 = { 2, 23, 45, 67, 5, 27, 6, 7, 12, 21, 67, 89 };

 /**
  * Sorting of complexity O(nlogn)
  */
 public static void main(String[] args) {
  System.out.println("\n==========Iterative Quicksort============");
  int[] input1 = { 2, 23, 5, 27, 6, 7, 12, 21 };
  System.out.println("Before sorting");
  for (int i = 0; i < input1.length; i++) {
   System.out.print(input1[i] + " ");
  }
  iterativeQuicksort(input1, 0, input1.length - 1);
  System.out.println("\n\nAfter sorting");
  
  for (int i = 0; i < input1.length; i++) {
   System.out.print(input1[i] + " ");
  }
 }
 // iterative quick sort
 public static void iterativeQuicksort(int[] input, int low, int high) {
  Stack<Integer> stack = new Stack<Integer>();
  stack.push(low);
  stack.push(high);
  while (!stack.isEmpty()) {
   int h = stack.pop();
   int l = stack.pop();
   int partionIndex = partition(input, l, h, input[h]);
   if (partionIndex - 1 > l) {
    stack.push(l);
    stack.push(partionIndex - 1);
   }
   if (partionIndex + 1 < h) {
    stack.push(partionIndex + 1);
    stack.push(h);
   }
  }
 }

 private static int partition(int[] input, int low, int high, int pivot) {
  int left = low - 1;
  int right = high;
  while (true) {
   while (input[++left] < pivot && left < right)
    ;
   while (input[--right] > pivot && right > 0)
    ;
   if (left <= right)
    Util.swap(left, right, input);
   else
    break;
  }
  Util.swap(left, high, input);
  return left;
 }
}
class Util {
 @SuppressWarnings("unused")
 public static void swap(int i, int j, int[] arr) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
 }
}

Sample output:-
C:\java-sample> javac HeapSortIterative.java
C:\java-sample> java HeapSortIterative

==========Iterative Quicksort============
Before sorting
2 23 5 27 6 7 12 21

After sorting
2 5 6 7 12 21 23 27

Staircase problem : Recursive and Dynamic programming solution (Sample code in Python)

Problem:- Top of staircases can be reached by climbing 1,2 or 3 steps at a time.How many ways there are to reach the top of the staircase. i.e: find number of ways to climb top of staircase.

Sample program to count total number of ways to reach top of staircase:- Recursive and Dynamic programming approach 

#find number of ways to reach at top of staircase with 1, 2 or 3 steps
def find_staircase_recur(n):
    if n ==0 or n ==1:
        return 1;
    elif n==2 : #(1,1|2) 2 ways 
        return 2;
    elif n == 3: #(1,2| 1,1,1|2,1|3) 4 ways 
        return 4
    else :
        return find_staircase(n-1) + find_staircase(n-2) + find_staircase(n-3) 

#build dp table in bottom-up approach
def find_staircase_dp(n):
    table=[]
    #insert base case
    table.insert(0,1);
    table.insert(1,1);
    table.insert(2,2); #(1,1|2) 2 ways 
    table.insert(3,4); #(1,2| 1,1,1|2,1|3) 4 ways 
    #Iterate if N >= 4
    for i in range(4,n+1):
        val = table[i-1] + table[i-2] +table[i-3]
        table.insert(i,val);
    return table[n]
print "Enter height of stair(Number of steps)"
n = int(raw_input().strip())
print "Number of ways to reach top of stair using 1, 2 or 3 steps are: "
print find_staircase_dp(n)

Explanation:- function find_staircase_recur is recursive way of counting no of ways and function find_staircase_dp is using bottom-up memoization approach to build DP table and remember pre-computed value.

Sample output:-
>>>
Enter height of stair(Number of steps)
7
Number of ways to reach top of stair using 1, 2 or 3 steps are:
44

>>>
Enter height of stair(Number of steps)
9
Number of ways to reach top of stair using 1, 2 or 3 steps are:
149

Reference : http://ms.appliedprobability.org/data/files/Articles%2047/47-1-4.pdf

Sort array of objects using Comparator in python

Problem:- Given an array of  Student objects, sort array using a comparator that sorts them in order of decreasing marks; if  or more students have the same marks, sort those students alphabetically by name.
Input :- Array of Student objects(Student object { Name; Marks;})
amy 90
ckm 90
nikhil 50
shweta 75
ranjan 150

Output:- Sort based on Marks (Name alphabetically if  marks is same)
ranjan  150
amy    90
ckm   90
shweta  75
nikhil    50

Sample program to sort list of student objects by passing comparator

class Students:
    def __init__(self, name, marks):
        self.name = name
        self.marks = marks 
    def comparator(a, b):
        if a.marks != b.marks :
            if a.marks < b.marks :
                return 1
            elif a.marks > b.marks:
                return -1
            else :
                return 0
        else:
            if a.name > b.name :
                return 1
            elif a.name < b.name:
                return -1
            else :
                return 0

print "Enter number of students "
n = int(raw_input())

data = []
for i in range(n):
    print "Enter Name and marks of student %d" %(i+1)
    name, marks = raw_input().split()
    marks = int(marks)
    player = Students(name, marks)
    data.append(player)
    
data = sorted(data, cmp=Students.comparator)
print "\nStudents Name and marks in sorted form "
print "Name \t Marks"
print "----------------"
for i in data:
    print i.name+ " \t "+ str(i.marks)

Sample output:-
>>>
Enter number of students
5
Enter Name and marks of student 1
amy 90
Enter Name and marks of student 2
ckm 90
Enter Name and marks of student 3
nikhil 50
Enter Name and marks of student 4
shweta 75
Enter Name and marks of student 5
ranjan 150

Students Name and marks in sorted form
Name Marks
----------------
ranjan 150
amy 90
ckm 90
shweta 75
nikhil 50

Python: Using XOR operator find unique elements in array

Problem:- Consider an array of  integers, , where every element in  occurs exactly twice except for one unique element.Find and print the unique element.

Input :- 4 9 95 93 57 4 57 93 9 #Input array with 95 as unique element.

Output:- 95

Background of XOR operator ( ^ ) :-  Bit-wise operator which results zero, if XOR operator is applied between same bits otherwise gives 1.

XOR Operator operation 

We can use XOR operation to reset all bit for two numbers , if they are same.  i.e : 3 ^ 3 = 0

Sample program to print unique element using XOR :-

#!/bin/python

def lonely_integer(a):
    storage = a[0]
    for i in range(1, a.__len__()):
        storage = storage ^ a[i]
    #print (storage)
    return storage
print "Enter size of array (Input) "
n = int(raw_input().strip())
print "Enter elements separated by space "
a = map(int,raw_input().strip().split(' '))
print "Unique element is "
print lonely_integer(a)

Sample output:-
>>>
Enter size of array (Input)
9
Enter elements separated by space
4 9 95 93 57 4 57 93 9
Unique element is
95