Skip to content

Updated QuickSort.java #87

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 2 commits into from
Aug 27, 2017
Merged

Updated QuickSort.java #87

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
e9b1e25
Updated QuickSort.java
varunu28 Aug 21, 2017
146a08c
Updated MergeSort.java
varunu28 Aug 25, 2017
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
155 changes: 73 additions & 82 deletions Sorts/MergeSort.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,109 +1,100 @@
import java.util.Scanner;

/**
* This class implements MergeSort
* @author Unknown
*
* @author Varun Upadhyay (https://github.com/varunu28)
*
*/
public class MergeSort {
/** Array for mergeSort*/
private int[] array;
/** Temp Merge Array*/
private int[] tempMergArr;
/** Length of the array*/
private int length;

/**
* Sorts inputArr with merge sort algorithm
*
* @param inputArr Array to be sorted
*/
public final void sort(int inputArr[]) {
this.array = inputArr;
this.length = inputArr.length;
this.tempMergArr = new int[this.length];
this.mergeSort(0, this.length - 1);
}
class MergeSort {

/**
* Partitions Array into recursively smaller pieces
* This method implements the Generic Merge Sort
*
* @param lowerIndex lower bound to include in the first partition
* @param higherIndex upper bound to include in the third partition
*/
private void mergeSort(int lowerIndex, int higherIndex) {
if (lowerIndex < higherIndex) {
int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
// Below step sorts the left side of the array
this.mergeSort(lowerIndex, middle);
// Below step sorts the right side of the array
this.mergeSort(middle + 1, higherIndex);
// Now merge both sides
this.mergeParts(lowerIndex, middle, higherIndex);
* @param arr The array to be sorted
* @param temp The copy of the actual array
* @param left The first index of the array
* @param right The last index of the array
* Recursively sorts the array in increasing order
**/

public static <T extends Comparable<T>> void MS(T[] arr, T[] temp, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
MS(arr, temp, left, mid);
MS(arr, temp,mid + 1, right);
merge(arr, temp, left, mid, right);
}

}

/**
* Merges partitions
* This method implements the merge step of the merge sort
*
* @param lowerIndex The lower index
* @param middle The middle index
* @param higherIndex The higher index
*/
private void mergeParts(int lowerIndex, int middle, int higherIndex) {
for (int i = lowerIndex; i <= higherIndex; i++) {
this.tempMergArr[i] = this.array[i];
* @param arr The array to be sorted
* @param temp The copy of the actual array
* @param left The first index of the array
* @param mid The middle index of the array
* @param right The last index of the array
* merges two parts of an array in increasing order
**/

public static <T extends Comparable<T>> void merge(T[] arr, T[] temp, int left, int mid, int right) {
for (int i=left;i<=right;i++) {
temp[i] = arr[i];
}
int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex) {
if (this.tempMergArr[i] <= this.tempMergArr[j]) {
this.array[k] = this.tempMergArr[i];

int i= left;
int j = mid + 1;
int k = left;

while (i<=mid && j<=right) {
if (temp[i].compareTo(temp[j]) <= 0) {
arr[k] = temp[i];
i++;
} else {
this.array[k] = this.tempMergArr[j];
}
else {
arr[k] = temp[j];
j++;
}
k++;
}
while (i <= middle) {
this.array[k] = this.tempMergArr[i];
k++;

while (i <= mid) {
arr[k] = temp[i];
i++;
k++;
}

}

/**
* Gets input to sort
*
* @return unsorted array of integers to sort
*/
public static int[] getInput() {
final int numElements = 6;
int[] unsorted = new int[numElements];
Scanner input = new Scanner(System.in);
System.out.println("Enter any 6 Numbers for Unsorted Array : ");
for (int i = 0; i < numElements; i++) {
unsorted[i] = input.nextInt();
// Driver program
public static void main(String[] args) {

// Integer Input
int[] arr = {4,23,6,78,1,54,231,9,12};
Integer[] array = new Integer[arr.length];
for (int i=0;i<array.length;i++) {
array[i] = arr[i];
}
input.close();
return unsorted;
}

/**
* Main Method
*
* @param args Command line arguments
*/
public static void main(String args[]) {
int[] inputArr = getInput();
MergeSort mergeSort = new MergeSort();
mergeSort.sort(inputArr);
for (int i : inputArr) {
System.out.print(i);
System.out.print(" ");
// Copy of actual array
Integer[] temp = new Integer[arr.length];

MS(array, temp, 0, arr.length-1);

// Output => 1 4 6 9 12 23 54 78 231
for (int i=0;i<arr.length;i++) {
System.out.print(array[i] + " ");
}
System.out.println();

// String Input
String[] array1 = {"c", "a", "e", "b","d"};
String[] temp1 = new String[array1.length];
MS(array1, temp1, 0, array1.length-1);

//Output => a b c d e
for(int i=0; i<array1.length; i++)
{
System.out.print(array1[i]+"\t");
}
}
}
93 changes: 93 additions & 0 deletions Sorts/QuickSort.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,93 @@
/**
*
* @author Varun Upadhyay (https://github.com/varunu28)
*
*/

class QuickSort {

/**
* This method implements the Generic Quick Sort
*
* @param array The array to be sorted
* @param start The first index of an array
* @param end The last index of an array
* Sorts the array in increasing order
**/

public static <T extends Comparable<T>> void QS(T array[], int start, int end) {
if (start < end) {
int PIndex = partition(array, start, end);
QS(array, start, PIndex - 1);
QS(array, PIndex + 1, end);
}
}

/**
* This method finds the partition index for an array
*
* @param array The array to be sorted
* @param start The first index of an array
* @param end The last index of an array
* Finds the partition index of an array
**/

public static <T extends Comparable<T>> int partition(T array[], int start, int end) {
T pivot = array[end];
int PIndex = start;
for (int i=start;i<end;i++) {
if (array[i].compareTo(pivot) <= 0) {
swap(array, i, PIndex);
PIndex++;
}
}
swap(array, PIndex, end);
return PIndex;
}

/**
* This method swaps two elements of an array
*
* @param array The array to be sorted
* @param initial The first element
* @param fin The second element
* Swaps initial and fin element
**/

public static <T extends Comparable<T>> void swap(T[] array, int initial, int fin) {
T temp = array[initial];
array[initial] = array[fin];
array[fin] = temp;
}

// Driver Program
public static void main(String[] args) {

// For integer input
int[] arr = {3,4,1,32,0,2,44,111,5};
Integer[] array = new Integer[arr.length];
for (int i=0;i<arr.length;i++) {
array[i] = arr[i];
}

QS(array, 0, arr.length-1);

//Output => 0 1 2 3 4 5 32 44 111
for (int i=0;i<array.length;i++) {
System.out.print(array[i] + " ");
}
System.out.println();

// String Input
String[] array1 = {"c", "a", "e", "b","d"};

QS(array1, 0,array1.length-1);

//Output => a b c d e
for(int i=0; i<array1.length; i++)
{
System.out.print(array1[i]+"\t");
}
}
}

102 changes: 0 additions & 102 deletions Sorts/Quicksort.java
View file
Open in desktop

This file was deleted.