sorting Archives - copypasteearth

Merge Sort algorithm with Generics that implement Comparable interface

Sorting algorithms are used everyday to sort all types of information in computer programs so I decided to share a O(Nlog2N) sorting algorithm called Merge Sort with you today. This is written in Java Programming. I shared a post last year on Quick Sort algorithm and I just decided to do all of the Big-O (Nlog2N) sorting algorithms. Of course Java has many built in data structures and uses the best sorting algorithms already, but if you are learning about data structures and algorithms you might find this post handy.

First I will post the Circle class just like in the Quicksort example that can be found here by the way QuickSort sorting algorithm in java with Generics that implement Comparable

Circle.java

/**
 * author: copypasteearth
 * date: 7/17/2019
 */
public class Circle implements Comparable<Circle> {
    public int xValue;
    public int yValue;
    public int radius;

@Override
public int compareTo(Circle o) {
return (this.radius - o.radius);
}
@Override
public String toString() {
return "x: " + xValue + " ---y: " + yValue + " ---radius: " + radius;
}
}

Secondly you are going to need the MergeSort class which also has the main method inside it so it can run the program. The class has static methods called merge and mergeSort that do all of the work. They basically keep splitting and sorting the array untill everything is sorted and then merges it all back together.

MergeSort.java

import java.util.Arrays;
import java.util.Random;

/**
* author: copypasteearth
* date: 7/17/2019
*/
public class MergeSort<T extends Comparable<T>> {

public static <T extends Comparable<T>> void merge(int leftFirst, int leftLast, int rightFirst, int rightLast, T[] array){
T[] tempArray = Arrays.copyOf(array,array.length);
int index = leftFirst;
int saveFirst = leftFirst;

while((leftFirst <= leftLast) && (rightFirst <= rightLast)){
if(array[leftFirst].compareTo(array[rightFirst]) < 0){
tempArray[index] = array[leftFirst];
leftFirst++;
}else{
tempArray[index] = array[rightFirst];
rightFirst++;
}
index++;
}
while(leftFirst <= leftLast){
tempArray[index] = array[leftFirst];
leftFirst++;
index++;
}
while(rightFirst <= rightLast){
tempArray[index] = array[rightFirst];
rightFirst++;
index++;
}
for(index = saveFirst; index <= rightLast;index++){
array[index] = tempArray[index];
}
}
public static <T extends Comparable<T>> void mergeSort(int first, int last,T[] array){
if(first < last){
int middle = (first + last) / 2;
mergeSort(first,middle,array);
mergeSort(middle+1,last,array);
merge(first,middle,middle+1,last,array);
}
}

public static void main(String[] args){
Circle[] circlearray = new Circle[20];
Random rand = new Random();
for (int index = 0; index < 20; index++)
{
circlearray[index] = new Circle();
circlearray[index].xValue = Math.abs(rand.nextInt()) % 100;
circlearray[index].yValue = Math.abs(rand.nextInt()) % 100;
circlearray[index].radius = Math.abs(rand.nextInt()) % 100;
}
System.out.println("Circle Array Unsorted....");
for(int i = 0;i < 20;i++){

System.out.println(circlearray[i]);
}
MergeSort<Circle> mscircle = new MergeSort<Circle>();
mscircle.mergeSort( 0, circlearray.length-1,circlearray);
System.out.println("Circle Array Sorted");
for(Circle i: circlearray) {
System.out.println(i);
}
}
}

And that pretty much sums it up for MergeSort. Another one of your should be favorited sorting algorithms that run at a whopping O(Nlog2N) complexity. Thanks for your time and i hope you liked this article and got some use out of it. I am leaving the Link to this and QuickSort on github here it is https://github.com/copypasteearth/Sorting

New Amazon Fire HD 8 tablet, 8” HD Display, 3GB memory, 32GB, designed for portable entertainment, Black, (2024 release)

(240)

$99.99 (as of November 19, 2024 02:53 GMT -05:00 - )

NSPENCM 85W Mac Book Pro Charger, Replacement AC 85w 2T-Tip Connector Power Adapter,Laptop Charger Compatible with MacBook pro & Mac Book Pro 13 inch-15 inch Retina After Mid 2012

(4417)

$18.99 (as of November 19, 2024 02:53 GMT -05:00 - )

45W USB-C Chromebook Charger for HP Chromebook X360 14 14-ca051wm 14-ca052wm 14-ca091wm ca061dx 14-ca0061dx 14-ca060nr 14-ca020nr 14-ca043cl USB C Power Supply Adapter

(1565)

$9.99 (as of November 19, 2024 02:53 GMT -05:00 - )

HP Chromebook 14 inch Laptop, FHD Display, Intel N100, 4 GB RAM, 64 GB eMMC, Intel UHD Graphics, Chrome OS 14a-nf0009nr (2024)

(69)

$209.00 (as of November 19, 2024 02:53 GMT -05:00 - )

Amazon Fire 7 Kids tablet (newest model) ages 3-7. Top-selling 7" kids tablet on Amazon | ad-free content with parental controls included, 10-hr battery, 16 GB, Purple

(21428)

$109.99 (as of November 19, 2024 02:53 GMT -05:00 - )

QuickSort sorting algorithm in java with Generics that implement Comparable

In this article I’m going to touch on the sorting algorithm called Quicksort. Its worst case time complexity is O(n^2) and its best case time complexity is O(nlogn). Firstly the method we are going to make is going to take a generic array and those elements should implement the Comparable interface so they can be sorted. Take this Circle class for example. When you implement the Comparable interface you specify in the compareTomethod what makes a circle greater than, less than, or equal to another circle. In this example we return whether the radius of the circle is bigger or smaller than the circle it is being compared to.

Circle.java

/**
 * author: copypasteearth
 * date: 7/17/2019
 */
public class Circle implements Comparable<Circle> {
    public int xValue;
    public int yValue;
    public int radius;

Next we create the Quicksort class that has the method quicksort and a main method to test out the quicksort method. The quicksort method is a recursive method and the base case is if(a < b). The method goes through the generic array and sorts the elements based on what the compareTo method tells it. Here is the Quicksort class.

Quicksort.java

/**
 * author: copypasteearth
 * date: 7/17/2019
 */
import java.util.Random;
public class QuickSort<T extends Comparable<T>> {

public static <T extends Comparable<T>> void quicksort(T[] array, int a, int b) {
if (a < b) {
int i = a, j = b;
T x = array[(i + j) / 2];

do {
while (array[i].compareTo(x) < 0) i++;
while (x.compareTo(array[j]) < 0) j--;

if ( i <= j) {
T tmp = array[i];
array[i] = array[j];
array[j] = tmp;
i++;
j--;
}

} while (i <= j);

quicksort(array, a, j);
quicksort(array, i, b);
}
}

public static void main(String[] args) {
Integer[] integerarray = {50, 55, 11, 89, 90, 1, 20, 11};
QuickSort<Integer> qsinteger = new QuickSort<Integer>();
qsinteger.quicksort(integerarray, 0, integerarray.length-1);
for(Integer i: integerarray) {
System.out.println(i);
}
String[] stringarray = {"bird","moth","apple","zebra","banana","desert","pig"};
QuickSort<String> qsstring = new QuickSort<String>();
qsstring.quicksort(stringarray, 0, stringarray.length-1);
for(String i: stringarray) {
System.out.println(i);
}
Circle[] circlearray = new Circle[20];
Random rand = new Random();
for (int index = 0; index < 20; index++)
{
circlearray[index] = new Circle();
circlearray[index].xValue = Math.abs(rand.nextInt()) % 100;
circlearray[index].yValue = Math.abs(rand.nextInt()) % 100;
circlearray[index].radius = Math.abs(rand.nextInt()) % 100;

}
System.out.println("Circle Array Unsorted....");
for(int i = 0;i < 20;i++){

System.out.println(circlearray[i]);
}
QuickSort<Circle> qscircle = new QuickSort<Circle>();
qscircle.quicksort(circlearray, 0, circlearray.length-1);
System.out.println("Circle Array Sorted");
for(Circle i: circlearray) {
System.out.println(i);
}

}

If you run this code you will see the results from the main method. First it sorts an Integer array and then a String array. Then it makes a Circle array and prints them out unsorted then it sorts them and then prints them out again sorted. That pretty much does it for this example on quicksorting. In the future I will probably go through the rest of the sorting algorithms. Hope you enjoyed it.

Donate or Subscribe to support Copypasteearth!!!!!