Thursday, February 12, 2015

QuickSort Algorithm: Without using sort

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import org.apache.commons.lang.ArrayUtils;

/** * Created by akhilgupta on 11-02-2015. */public class QuickSortSample {
    public static void main(String args[]){
       // int[] test = {32,23,43,2,33,12,33,11,45,56,88,10};        int[] test = {32,23,43,2,33,12,33,11,45,56,88,10,32,23,43,2,33,1,88,10,32,23,43,2,133,12,33,11,5,56,8,10};
        getQuickSort(test);
    }

    static void getQuickSort(int[] test) {
        List<Integer> lstLower = new ArrayList();
        List<Integer> lstUpper = new ArrayList();
        int[] lower={};
        int[] upper={};
        int pivot=0;
        //   lst.add(test);        for (int i = 0; i < test.length; i++) {
            pivot = test[(test.length - 1) / 2];
            int k = (test.length - 4) / 2;
        }
            for (int m = 0; m < test.length; m++) {
                if (test[m] < pivot)
                    lstLower.add(test[m]);
                else                    lstUpper.add(test[m]);
            }
             lower = ArrayUtils.toPrimitive(lstLower.toArray(new Integer[lstLower.size()]));
              upper = ArrayUtils.toPrimitive(lstUpper.toArray(new Integer[lstUpper.size()]));
            int temp = 0;
        List<Integer> sumList = new ArrayList<Integer>();
        sumList.addAll(swap(lower));
        sumList.addAll(swap(upper));
        Iterator<Integer> itr = sumList.listIterator();
        while(itr.hasNext()){
            Integer it = itr.next();
            System.out.print(" "+it+" ");

        }
    }

    public static List<Integer> swap(int[] test) {
        //int[] test = lower;        for (int m = test.length; m > 0; m--) {
            for (int i = 0; i < test.length - 1; i++) {
                int tmp = test[i + 1];
                if (test[i] > tmp) {
                    tmp = test[i];
                    test[i] = test[i + 1];
                    test[i + 1] = tmp;
                }
            }
        }
        List<Integer> finalList = new ArrayList<Integer>();
        for (int n = 0; n < test.length; n++) {
            finalList.add(test[n]);
        }

        System.out.println("\n");
        return finalList;
    }
    }











No comments:

Post a Comment