Kontera

Saturday, November 17, 2012

Qick Sort Using Java

/* Implementation of QUICK SORT ALGORITHM using JAVA
Date:         18/11/2012
Author :     Sarju S */

import java.util.*;
import java.io.*;

public class QuickSort{
    public static void main(String[] args) {
        try{
        System.out.println("\nEnter the total number of element to sort:");
        DataInputStream din  = new DataInputStream(System.in);
        din = new DataInputStream(System.in);
        int totalNumbers = Integer.parseInt(din.readLine());
        int array[] = new int[totalNumbers];
        System.out.println("Enter the elements: ");
        for(int i=0;i            array[i] = Integer.parseInt(din.readLine());
        }
        recursiveQuickSort(array, 0, array.length-1);
        System.out.println("The following array should be sorted: ");
        printList(array);
        System.exit(0);
        }
        catch(Exception e){
        }
    }

    public static void recursiveQuickSort(int[] list, int first, int last) {
        if(first < last)
        {
            int p = partition(list, first, last);
            printList(list);
            recursiveQuickSort(list, first, p-1);
            recursiveQuickSort(list, p+1, last);
        }
    }

    public static int partition(int[] list, int first, int last) {
        int p = first;
        for(int n = p+1; n <= last; n++)
            if(list[n] < list[p])
            {
                swap(list, n, p+1);
                swap(list, p, p+1);
                p++;
            }
        return p;
    }

    private static void swap(int[] list, int index1, int index2) {
        int temp = list[index1];
        list[index1] = list[index2];
        list[index2] = temp;
    }

    protected static void printList(int[] list) {
        for(int n = 0; n < list.length; n++)
            System.out.print(list[n]+" ");
        System.out.println();
    }
}

0 comments:

Post a Comment