Selection Sort

import java.util.List;

public class SelectionSort {
 /**
  * @param args
  */
 public static void main(String[] args) {
  List<Long> input = FileReader.getInputFromFile();
  System.out.println("Input Size :: " + input.size() );
  System.out.println(" INPUT ");
  for(Long number : input){
   System.out.print(number + ", ");
  }
  System.out.println();
  sort(input);
  System.out.println(" OUTPUT ");
  for(Long number : input){
   System.out.print(number + ", ");
  }
 }

 public static void sort(List<Long> input){
  for(int current=0; current < input.size()-1; current++){
   for(int next=current+1; next < input.size(); next++){
    if(input.get(next) < input.get(current)){
     Long temp = input.get(next);
     input.set(next, input.get(current));
     input.set(current, temp);
    }
   }
  
  }
 }
}

Graph - Min Cut Problem

This is little cluttered and demands cleanup. Will do shortly.

package com.me.algo.graphs;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

public class MinCut {

/**
* @param args
*/
public static void main(String[] args) {
Graph g = readGraphFromTextFile();
int totalVertices = g.getV().size();
int remainingVertices = totalVertices;
while(remainingVertices > 2){
int aRandomNumber = generateRandomInteger(0,remainingVertices-1, new Random());
Vertex selectedSource = g.getV().get(aRandomNumber);
int selectedDestination = selectedSource.getAdjList().get(0);
graphContract(g, selectedSource, selectedDestination);
remainingVertices--;
}
List<Vertex> allVertices = g.getV();
for(Vertex v : allVertices){
System.out.print(v.getNode()  );
List<Integer> adjNodes = v.getAdjList();
for(int node : adjNodes){
System.out.print(" " + node);
}
System.out.println(" Min Cut :: " + adjNodes.size());
}

}

public static void graphContract(Graph g, Vertex source, int destination ){
List<Vertex> allVertices = g.getV();
List<Integer> adjListOfSource = source.getAdjList();
for(Vertex v : allVertices){
if(v.getNode() == destination){
v.getAdjList().addAll(adjListOfSource);
}
}
for(Vertex v : allVertices){
if(v.getNode() != source.getNode()){ //source to be fused or deleted, so do not consider the source.
for(int node : adjListOfSource){
if(v.getNode() == node){
v.getAdjList().add(destination);
}
}
}
}
removeSourceEveryWhere(g, source);
removeSelfLoops(g);
}

private static void removeSourceEveryWhere(Graph g, Vertex source){
List<Vertex> allVertices = g.getV();
for(Vertex v : allVertices){
List<Integer> adjList = v.getAdjList();
List<Integer> newAdjNodes = new ArrayList<Integer>(adjList);
for(int adjNode : adjList){
if(adjNode == source.getNode()){
newAdjNodes.remove(new Integer(adjNode));
}
}
v.setAdjList(newAdjNodes);
}
allVertices.remove(source);
}

private static void removeSelfLoops(Graph g){
List<Vertex> allVertices = g.getV();
for(Vertex v : allVertices){
List<Integer> adjNodes = v.getAdjList();
List<Integer> newAdjNodes = new ArrayList<Integer>(adjNodes);
for(int adjNode : adjNodes){
if(adjNode == v.getNode()){
newAdjNodes.remove(new Integer(adjNode));
}
}
v.setAdjList(newAdjNodes);
}
}

private static Graph readGraphFromTextFile(){
//String filePath = "D:/AlgorithmSpace/Algo/src/com/me/algo/graphs/kargerAdj02.txt";
String filePath = "D:/AlgorithmSpace/Algo/src/com/me/algo/graphs/kargerAdj.txt";
Scanner scanner = null;
try{
scanner = new Scanner(new File(filePath));
}catch(FileNotFoundException fnfe){
System.out.println("File does not exist!!");
System.exit(0);
}
List<Vertex> vertices = new ArrayList<Vertex>();
while(scanner.hasNext()){
String vertexData = scanner.nextLine();
Vertex v = new Vertex();
Scanner vertexScanner = new Scanner(vertexData);
List<Integer> adjList = new ArrayList<Integer>();
boolean isNodeExtracted = false;
while(vertexScanner.hasNextInt()){
if(!isNodeExtracted){
v.setNode(vertexScanner.nextInt());
isNodeExtracted = true;
}
adjList.add(vertexScanner.nextInt());
}
v.setAdjList(adjList);
vertices.add(v);
}
scanner.close();
Graph g = new Graph();
g.setV(vertices);
return g;
}

private static int generateRandomInteger(int aStart, int aEnd, Random aRandom){
if ( aStart > aEnd ) {
throw new IllegalArgumentException("Start cannot exceed End.");
}
long range = (long)aEnd - (long)aStart + 1;
long fraction = (long)(range * aRandom.nextDouble());
int randomNumber =  (int)(fraction + aStart);
return randomNumber;
}

}

Inversion using mergesort

public class ListInversionFinder {

    /**
     * @param args
     */
    public static void main(String[] args) throws Exception{
        List<Long> input = TextFileReader.read();
        System.out.println(" INPUT ");
        for(long l : input){
            System.out.print(l + ", ");
        }
        System.out.println();
        long count = splitMerge(input, 0, input.size());
        System.out.println(" OUTPUT ");
        for(long l : input){
            System.out.print(l + ", ");
        }
        System.out.println();
        System.out.println("Inversion Count :: " + count);
    }

    public static long splitMerge(List data, int start, int length){
        long inversionCount = 0;
        if(length > 1) {
            int l = length/2;
            int l1 = length - l;
            long c = splitMerge(data, start, l);
            long c1 = splitMerge(data, start + l, l1);
            long count = merge(data, start, l, l1);
            inversionCount =  c + c1 + count;
        }
        return inversionCount;
    }

    private static long merge(List<Long> data, int start, int l, int l1){
        List<Long> temp = new ArrayList(l+l1);
        int i = 0;
        int j = 0 ;
        int k = 0;
        long inversionCount = 0;
        while(i < l && j < l1){
            if(data.get(start + i) <= data.get(start + l + j)){
                temp.add(k, data.get(start + i));
                i++;
            }
            else if(data.get(start + l + j) < data.get(start + i)){
                temp.add(k, data.get(start + l + j));
                j++;
                inversionCount = inversionCount + 1 + (l-(i+1));
            }
            k++;
        }
        while(j < l1){
            temp.add(k, data.get(start + l + j));
            j++;
            k++;
        }
        while(i < l){
            temp.add(k, data.get(start + i));
            i++;
            k++;
        }
        for(int m=0;m < temp.size();m++){
            int pos = start + m;
            data.set(pos, temp.get(m));
        }
        return inversionCount;
    }

}

MergeSort with list data structure

public class MergeSort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] input = new int[]{8,7,6,5,4,3,2,1,10};
        System.out.println(" INPUT :: "+ input);
        int[] output = splitMerge(input,0,input.length);
        for(int x=0;x < output.length;x++){
            System.out.print(" OUTPUT :: "+ output[x] + " ");
        }

    }
   
    public static int[] splitMerge(int[] data, int start, int length){
        if(length > 1) {
            int l = length/2;
            int l1 = length - l;
            splitMerge(data, start, l);
            splitMerge(data, start + l, l1);
            merge(data, start, l, l1);
        }
        return data;
    }
   
    private static void merge(int[] data, int start, int l, int l1 ){
        int[] temp = new int[l+l1];;
        int i = 0;
        int j = 0 ;
        int k = 0;
        while(i < l && j < l1){
            if(data[start + i] <= data[start + l + j]){
                temp[k] = data[start + i];
                i++;
            }
            else if(data[start + l + j] < data[start + i]){
                temp[k] = data[start + l + j];
                j++;
            }
            k++;
        }
        while(j < l1){
            temp[k] = data[start + l + j];
            j++;
            k++;
        }
        while(i < l){
            temp[k] = data[start + i];
            i++;
            k++;
        }
        for(int m=0;m < temp.length;m++){
            data[start + m] = temp[m];
        }
        System.out.println();
    }
}

MergeSort with primitive array

Running time - O(n log n)

Java Implementation with primitive array

public class MergeSort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] input = new int[]{8,7,6,5,4,3,2,1,10};
        System.out.println(" INPUT :: "+ input);
        int[] output = splitMerge(input,0,input.length);
        for(int x=0;x < output.length;x++){
            System.out.print(" OUTPUT :: "+ output[x] + " ");
        }

    }
   
    public static int[] splitMerge(int[] data, int start, int length){
        if(length > 1) {
            int l = length/2;
            int l1 = length - l;
            splitMerge(data, start, l);
            splitMerge(data, start + l, l1);
            merge(data, start, l, l1);
        }
        return data;
    }
   
    private static void merge(int[] data, int start, int l, int l1 ){
        int[] temp = new int[l+l1];;
        int i = 0;
        int j = 0 ;
        int k = 0;
        while(i < l && j < l1){
            if(data[start + i] <= data[start + l + j]){
                temp[k] = data[start + i];
                i++;
            }
            else if(data[start + l + j] < data[start + i]){
                temp[k] = data[start + l + j];
                j++;
            }
            k++;
        }
        while(j < l1){
            temp[k] = data[start + l + j];
            j++;
            k++;
        }
        while(i < l){
            temp[k] = data[start + i];
            i++;
            k++;
        }
        for(int m=0;m < temp.length;m++){
            data[start + m] = temp[m];
        }
        System.out.println();
    }

}

QuickSort - First element as Pivot

The code helps the choose the first element as the pivot in the partition subroutine.


package com.me.algo.sort;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class QuickSort1Approach2 {

private static long totalComparisons;

/**
* @param args
*/
public static void main(String[] args) {
List<Long> input = getInputFromFile();
System.out.println("Input Size :: " + input.size() );
System.out.println(" INPUT ");
for(Long number : input){
System.out.print(number + ", ");
}
System.out.println();
quickSort(input, 0, input.size()-1);
System.out.println(" OUTPUT ");
for(Long number : input){
System.out.print(number + ", ");
}
System.out.println();
System.out.println(" Total Number Of Comparisons " + totalComparisons);
}

public static void quickSort(List<Long> input, int left, int right){
int currentIndex = partitionWithFirstPivot(input, left, right);
if(left < currentIndex - 1){
quickSort(input, left, currentIndex-1);
totalComparisons = totalComparisons + (currentIndex - 2 - left);
}
if(right > currentIndex + 1){
quickSort(input, currentIndex + 1, right);
totalComparisons = totalComparisons + (right - currentIndex);
}
}

public static int partitionWithFirstPivot(List<Long> input, int left, int right){
long pivot = input.get(left);
int i = left + 1;
for(int j = left+1; j <= right; j++){
if(input.get(j) < pivot){
long temp = input.get(j);
input.set(j, input.get(i));
input.set(i, temp);
i++;
}
}
input.set(left, input.get(i-1));
input.set(i-1, pivot);
return i - 1;
}

private static List<Long> getInputFromFile(){
List<Long> input = new ArrayList<Long>();
//String filePath = "D:/AlgorithmSpace/Algo/src/com/me/algo/sort/input_01.txt";
String filePath = "D:/AlgorithmSpace/Algo/src/com/me/algo/sort/QuickSortInput_02.txt";
Scanner scanner = null;
try{
scanner = new Scanner(new File(filePath));
}catch(FileNotFoundException fnfe){
System.out.println("File does not exist!!");
System.exit(0);
}
while(scanner.hasNext()){
Long data = scanner.nextLong();
System.out.println(data);
input.add(data);
}
scanner.close();
return input;
}

}