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.
