August232011

Moar Sorting

To continue from before, I’m now up to 6/13 sorting algorithms.
Below will be the new ones in Python and then everything in Java flavor.

def bubble_sort(a):
    done = 0
    while(done == 0):
        count = 0
        for i in range(len(a)-1):
            if(a[i+1] < a[i]):
                #swap
                temp = a[i]
                a[i] = a[i+1]
                a[i+1] = temp
                #record swap
                count += 1
        if(count == 0):
            done = 1

def comb_sort(a):
    shrink = 1.3
    gap = int(len(a)/shrink)
    done = 0
    while(done == 0):
        count = 0
        for i in range(len(a)-gap):
            if(a[i+gap] < a[i]):
                #swap
                temp = a[i]
                a[i] = a[i+gap]
                a[i+gap] = temp
                #record swap
                count += 1
            #done one swap, going for the next value
        #done one cycle, getting new gap
        if(gap != 1):
            gap = int(gap/shrink)
        else:
            if(count == 0):
                done = 1

def quick_sort(a):
    if(len(a) < 2):
        return a
    else:
        # set up
        less = []
        more = []
        pivot_point = len(a)/2
        pivot_val = a.pop(pivot_point)
        # splitting
        for i in range(len(a)):
            if(a[i] <= pivot_val):
                less.append(a[i])
            else:
                more.append(a[i])
        less = quick_sort(less)
        more = quick_sort(more)
        less.append(pivot_val)
        # assembly
        result = []
        for x in range(len(less)):
            result.append(less[x])
        for y in range(len(more)):
            result.append(more[y])
        return result

In Java:

    // in-place sorting: simple
    public static void selection_sort(int[] a) {
        // accessing each index
        for (int i = 0; i < a.length; i++) {
            // find index of smallest value in the remaining indices
            int mindex = i; 
            for (int j = i; j < a.length; j++) {
                if(a[j] < a[mindex]) {
                    mindex = j;
                }
            }
            // swap i and mindex
            int temp = a[i];
            a[i] = a[mindex];
            a[mindex] = temp;
        }
    }

    // in-place sorting
    public static void insertion_sort(int[] a) {
        if(a.length > 1) {
            // start at 2nd index
            for (int i = 1; i < a.length; i++) {
                int si = i;
                for (int j = i-1; j >= 0; j--) {
                    if(a[si] < a[j]) {
                        // swap
                        int temp = a[si]; a[si] = a[j]; a[j] = temp;
                        si = j;
                    }
                }
            }
        }
    }

    // in-place sorting: simple
    public static void bubble_sort(int[] a) {
        boolean need_sorting = true;
        // only stop when no pairs of elements can be swapped 
        while(need_sorting) {
            int count = 0; // number of swaps
            for (int i = 0; i < a.length-1; i++) {
                if(a[i] > a[i+1]) {
                    // swap i and i+1
                    int temp = a[i];
                    a[i] = a[i+1];
                    a[i+1] = temp;
                    count++; // record swap count
                }
            }
            if(count == 0) {
                need_sorting = false;
            }
        }
    }

    // in-place sorting: upgrade of bubble_sort
    public static void comb_sort(int[] a) {
        boolean done = false;
        // defining the swap gap
        double shrink_factor = 1.3;
        int gap = (int) (a.length/shrink_factor);
        while(!done) {
            int count = 0;
            for (int i = 0; i < a.length-gap; i++) {
                if(a[i] > a[i + gap]) {
                    // swap
                    int temp = a[i]; a[i] = a[i+gap]; a[i+gap] = temp;
                    count++;
                }
            }
            // update the gap
            while (gap != 1) {
                gap = (int) (gap/shrink_factor);
            }
            if(count == 0) {
                done = true;
            }
        }
    }

    // recursive sorting
    public static int[] merge_sort(int[] a) {
        // base cases:
        if(a.length < 2) {
            return a;
        }
        else {
             // beware: floor/ceil receives both double and int values
            int[] left = new int[(int) Math.floor(a.length/2.0)]; 
            int[] right = new int[(int) Math.ceil(a.length/2.0)];
            for (int i = 0; i < left.length; i++) {
                left[i] = a[i]; // copy a's first half to left
            }
            for (int i = 0; i < right.length; i++) {
                right[i] = a[i + a.length/2]; // b's second half to right
            }
            // recursively sort until base cases
            left = merge_sort(left);
            right = merge_sort(right);
            // concatenate left and right into a in a sorted manner
            merge(a, left, right);
            return a;
        }
    }
    private static int[] merge(int[] result, int[] left, int[] right) {
        int i=0, j=0, k=0;
        while (i < left.length) {
            // as long as right's first ele < left's first ele
            // add right's to result, otherwise, break out of loop 
            // and add left's
            while (j < right.length && right[j] < left[i]) {
                result[k] = right[j];
                j++; k++;
            }
            // left[i] < right[j] here
            result[k] = left[i];
            i++; k++;
        }
        // leftover right elements (if any)
        if(j < right.length) {
            for (int l = j; l < right.length; l++) {
                result[k] = right[l];
                k++;
            }
        }
        return result;
    }

    public static int[] quick_sort(int[] a) {
        if(a.length < 2) {
            return a; // base cases
        }
        else {
            // choose pivot point
            int pindex = a.length/2;
            // count values less than a[pindex]
            int count = 0;
            for (int i = 0; i < a.length; i++) {
                if(a[i] < a[pindex]) {
                    count++;
                }
            }
            // divide, excluding pindex
            int[] small = new int[count]; int j=0;
            int[] large = new int[a.length - (count+1)]; int k=0;
            for (int i = 0; i < a.length; i++) {
                if(i != pindex) { // excluding pindex
                    if((a[i] < a[pindex])) {
                        small[j] = a[i]; j++;
                    }
                    else {
                        large[k] = a[i]; k++;
                    }
                }
            }
            // done splitting, further split then reconstruct
            return concatenate(quick_sort(small), a[pindex], quick_sort(large));
        }
    }
    // to be used to assist quick_sort
    private static int[] concatenate (int[] small, int pval, int[] large) {
        int[] result = new int[small.length + large.length + 1];
        for (int i = 0; i < small.length; i++) {
            result[i] = small[i];
        }
        result[small.length] = pval;
        for (int i = 0; i < large.length; i++) {
            result[i + (small.length+1)] = large[i];
        }
        return result;
    }

Since this is already too long a post, I’ll do a more dedicated post for each of these algorithms.

Page 1 of 1