Labels

algorithms (22) Design Patterns (20) java (19) linux (14) Snippet (13) service mix (6) soa (4)

Quick Sort in Java

 private static void quickSort(Integer[] toSortArray, int low, int high) {
        if (low >= high)
            return;
        int k = partition(toSortArray, low, high);
        quickSort(toSortArray, low, k - 1);
        quickSort(toSortArray, k + 1, high);
    }
    /**
     * given a number index low, it partitions array 
     * such that all numbers less than numbers[]low] are left
     * and greater are right
     * @param numbers
     * @param low
     * @param high
     * @return
     */
    private static int partition(Integer[] numbers, int low, int high) {
        int leftIndex = low;
        int rightIndex = high + 1;
        while (true) {            
            //find left index to swap
            while (numbers[++leftIndex] < numbers[low]) {
                if (leftIndex == high) {
                    break;
                }
            }
            //find right index to swap
            while (numbers[low] < numbers[--rightIndex]) {
                if (rightIndex == low) {
                    break;
                }
            }
            // pointers cross
            if (leftIndex >= rightIndex)
                break;
            //swap
            swap(leftIndex, rightIndex, numbers);
        }
        swap(low, rightIndex, numbers);
        return rightIndex;
    }
    private static void printArray(Integer[] toSortArray) {
        for (int i = 0; i < toSortArray.length; i++) {
            System.out.print(toSortArray[i] + " ");
        }
        System.out.println(" ");
    }
    /**
     * swap 2 numbers at the index
     * 
     * @param minIndex
     * @param index
     * @param numbers
     */
    private static void swap(int minIndex, int index, Integer[] numbers) {
        Integer temp = numbers[minIndex];
        numbers[minIndex] = numbers[index];
        numbers[index] = temp;
    }

No comments:

Post a Comment

Search 24 Bytes

Loading...