Sorting

Sorting.groovy

def arr  = [2,1,7,9,8,6,4,5,10,3]
// initial state of the array
println arr

// bubble up the largest element for each increment of the outer loop 
def bubbleSort(arr) {
    for (int i = 0 ; i < arr.size() - 1; i++) {
        for (int j = 0 ; j < (arr.size() - i -1 ); j++) {
            if (arr[j] > arr[j+1]){
                def tmp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = tmp               
            }
            println i +"=>"+ arr
        }
    }
}

// find largest or smallest put it in right position
def selectionSort(arr) {
    for (int i = 0 ; i < arr.size()-1 ; i++) {
        int min = i;
        for (int  j = i+1; j < arr.size() ; j++) {
            if (arr[min] > arr[j])
                min = j
        }
        // swap
        if (i != min)
            swap(arr, i , min)
        println i +"=>"+ arr
    }
}

def swap(arr, pos1, pos2){
    def tmp = arr[pos1]
    arr[pos1] = arr[pos2]
    arr[pos2] = tmp
}

// insert element at right position of the left sub array
def insertionSort(arr) {
    for (int i = 1 ; i < arr.size(); i++) {
        def ele = arr[i]
        def j = i
        while (j > 0 && ele < arr[j-1]) {            
            def tmp = arr[j-1]
            arr[j-1] = arr[j]
            arr[j] = tmp 
            j--;
            println i +"=>"+arr
        }
        if (j == i)
            println i +"!=>"+arr
                
    }
}

// divide and conquer - nlogn
def mergeSort(arr, left, right) {
    if (left < right) {
        //println "mergeSort ->" + left + " " + right 
        int middle = ((left + right)/2)
        mergeSort(arr, left, middle) // 0, 1
        mergeSort(arr, middle+1, right) // 2 , 2
        merge(arr, left, middle, right) // 0 , 1 , 2
    }
}

def merge(arr, left, middle, right) {
    int ll = left    
    int rl = middle +1
    int  k = 0;
    def tmpArr = [] // right - left + 1
    while (k < (right - left + 1)) {
        if (ll > middle)
            tmpArr[k++] = arr[rl++]
        else if (rl > right)
            tmpArr[k++] = arr[ll++]
        else if (arr[ll] < arr[rl]) 
            tmpArr[k++] = arr[ll++]
        else
            tmpArr[k++] = arr[rl++]
            // counter += middle - ll + 1;
    }
    k = 0
    for (int i = left ; i <= right; i++) {
        arr[i] = tmpArr[k++]
    }
    println arr
}

// take a pivot and partition the array 
// with all lesser elements on left and larger elemnents on the right of pivot
def quickSort(arr, lo, hi) {
    if (lo < hi) {
        def pivotPos = partition(arr, hi)
        quickSort(arr, lo, pivotPos-1)
        quickSort(arr, pivotPos+1, hi)
    }
}

// 7 8 2
def partition(arr, pivotPos) {
    def pivot = pivotPos;
    for (int i = pivotPos-1; i >= 0; i--) {        
        if (arr[pivot] < arr[i]) {            
            // swap
            //for (int j = i; j < pivot; j++){
                def tmp = arr[i]
                arr[i] = arr[i+1]
                arr[i+1] = tmp;
                println pivotPos +"=>" +arr
            //}
            pivot = i
        }
    }
    return pivot
}

def max_heapify(arr, i, N) { // 5. 10
    def left = 2*i + 1 // 10
    def right = 2*i + 2 // 11
    def largest = i
    if (left < N && arr[left] > arr[i]) {
        largest = left
    }
    
    if (right < N && arr[right] > arr[largest]) {
        largest = right
    }
    
    if (largest != i) {
        // swap arr[i] and arr[largest]
        def tmp = arr[i]
        arr[i] = arr[largest]
        arr[largest] = tmp
        max_heapify(arr, largest, N)
    }
}

def build_max_heap(arr) {
    for (int i = arr.size()/2 - 1 ; i >= 0  ; i--){
        max_heapify(arr, i, arr.size())
    }
}

def heapSort(arr) {
    def heapSize = arr.size()
    build_max_heap(arr)
    println arr
    for (int i = heapSize-1 ; i>= 0  ; i--){
        // swap largest element
        def tmp = arr[i]
        arr[i] = arr[0]
        arr[0] = tmp
        println arr
        max_heapify(arr, 0, i);
        println arr
    }
}

//bubbleSort(arr)
//selectionSort(arr)
//insertionSort(arr)
//mergeSort(arr, 0, arr.size()-1)
//quickSort(arr, 0, arr.size()-1)
//heapSort(arr)