Created
August 17, 2021 22:00
-
-
Save emmaline261b/979c1cbbb1f0bafe8d760861fb272a1f to your computer and use it in GitHub Desktop.
Sorting Methods for int arrays (selection sort and merge sort)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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