Skip to content

Instantly share code, notes, and snippets.

@emmaline261b
Created August 17, 2021 22:00
Show Gist options
  • Save emmaline261b/979c1cbbb1f0bafe8d760861fb272a1f to your computer and use it in GitHub Desktop.
Save emmaline261b/979c1cbbb1f0bafe8d760861fb272a1f to your computer and use it in GitHub Desktop.
Sorting Methods for int arrays (selection sort and merge sort)
import java.util.Arrays;
import java.util.Scanner;
public class MergeSort {
public static void main(String[] args) {
int lentghOfArray = 0;
Scanner input = new Scanner(System.in);
System.out.println("What's the size of the array?");
//checks if the user gave an integer;
boolean isInteger = false;
while (!isInteger) {
if (input.hasNextInt()) {
lentghOfArray = input.nextInt();
isInteger = true;
} else
System.out.println("Wrong input. Try again.");
input.nextLine();
}
//creates the array and asks for input.
int[] arrayOfInts = new int[lentghOfArray];
//Asks the user for the integers for the array;
System.out.printf("Write %d integers.\n", lentghOfArray);
for (int i = 0; i < lentghOfArray; i++) {
isInteger = false;
while (!isInteger) {
if (input.hasNextInt()) {
arrayOfInts[i] = input.nextInt();
isInteger = true;
} else
System.out.println("Wrong input. Try again.");
input.nextLine();
}
}
System.out.println("Unsorted Array: " + Arrays.toString(arrayOfInts));
System.out.println("==================");
arrayOfInts = DivideMethod(arrayOfInts);
System.out.println("Sorted Array: " + Arrays.toString(arrayOfInts));
}
//The method divides the original array into halves, goes into recursion and calls the merge method.
public static int[] DivideMethod (int[] array) {
//the condition to break the recursion
if (array.length <= 1) {
return array;
} else { //divides the original array into halves;
int midpoint = array.length / 2;
int[] arrayLeft = new int[midpoint];
for (int i = 0; i < midpoint; i++) {
arrayLeft[i] = array[i];
}
//copies the halves of the original array into new subarrays;
int[] arrayRight = new int[array.length - midpoint];
for (int i = 0; i < (array.length - midpoint); i++) {
arrayRight[i] = array[midpoint + i];
}
//goes into recursion;
arrayLeft = DivideMethod(arrayLeft);
arrayRight = DivideMethod(arrayRight);
//calls the merge method to sort the subarrays;
return MergeMethod(arrayLeft, arrayRight);
}
}
//The merge method sorts subarrays and returns a new array of combined subarrays' lengths;
public static int[] MergeMethod(int[] arrayLeft, int[] arrayRight) {
int[] resultArray = new int[arrayLeft.length + arrayRight.length];
int leftIndex, rightIndex, resultIndex;
leftIndex = rightIndex = resultIndex = 0;
//the loop to compare all the items of both arrays
while ((leftIndex < arrayLeft.length) || (rightIndex < arrayRight.length)) {
//as long as there are items in both arrays left to compare...
if ((leftIndex < arrayLeft.length) && (rightIndex < arrayRight.length)) {
if (arrayLeft[leftIndex] < arrayRight[rightIndex]) {
resultArray[resultIndex] = arrayLeft[leftIndex];
resultIndex++;
leftIndex++;
} else {
resultArray[resultIndex] = arrayRight[rightIndex];
resultIndex++;
rightIndex++;
}
// if one of the arrays have no items left to compare,
// the items from the other array are copied into the result array;
} else if (leftIndex < arrayLeft.length) {
resultArray[resultIndex] = arrayLeft[leftIndex];
resultIndex++;
leftIndex++;
} else if (rightIndex < arrayRight.length) {
resultArray[resultIndex] = arrayRight[rightIndex];
resultIndex++;
rightIndex++;
}
}
//returns the combined array of two subarrays;
return resultArray;
}
}
import java.sql.SQLOutput;
import java.util.Arrays;
import java.util.Scanner;
public class SelectionSort {
public static void main(String[] args) {
int lentghOfArray = 0;
Scanner input = new Scanner(System.in);
System.out.println("What's the size of the array?");
//checks if the user gave an integer;
boolean isInteger = false;
while (!isInteger) {
if (input.hasNextInt()) {
lentghOfArray = input.nextInt();
isInteger = true;
} else
System.out.println("Wrong input. Try again.");
input.nextLine();
}
//creates the array and asks for input.
int[] arrayOfInts = new int[lentghOfArray];
//Asks the user for the integers for the array;
System.out.printf("Write %d integers.\n", lentghOfArray);
for (int i = 0; i < lentghOfArray; i++) {
isInteger = false;
while (!isInteger) {
if (input.hasNextInt()) {
arrayOfInts[i] = input.nextInt();
isInteger = true;
} else
System.out.println("Wrong input. Try again.");
input.nextLine();
}
}
//Prints out the unsorted array.
System.out.println("Unsorted Array: " + Arrays.toString(arrayOfInts));
System.out.println("==================");
//Calls the selection sorting method;
arrayOfInts = SelectionSortMethod(arrayOfInts);
//Prints out the sorted array.
System.out.println("Sorted Array: " + Arrays.toString(arrayOfInts));
}
//The method finds the lowest number in the array and swaps it with the first unsorted item in the array.
public static int[] SelectionSortMethod(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
int tempValue = array[i];
int tempIndex = i;
for (int j = i + 1; j < array.length; j++) {
if (tempValue > array[j]) {
tempValue = array[j];
tempIndex = j;
}
}
array[tempIndex] = array[i];
array[i] = tempValue;
}
return array;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment