Created
January 27, 2015 18:34
-
-
Save kineticz/1218c1d5d4b7bbf5c0aa to your computer and use it in GitHub Desktop.
Any suggestions to simplify / improve this implementation of quicksort?
This file contains hidden or 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
| public static int[] concatArrays(int[] a1, int[] a2) { | |
| int n1 = a1.length; | |
| int n2 = a2.length; | |
| if(n1 == 0) return a2; | |
| if(n2 == 0) return a1; | |
| int n = n1 + n2; | |
| int counter = 0; | |
| int[] result = new int[n]; | |
| for(; counter < n1; counter++) { | |
| result[counter] = a1[counter]; | |
| } | |
| for(; counter < n; counter++) { | |
| result[counter] = a2[counter - n1]; | |
| } | |
| return result; | |
| } | |
| public static int[] concatArrays(int[] a1, int a2) { | |
| int[] a2New = new int[] {a2}; | |
| return concatArrays(a1, a2New); | |
| } | |
| public static int[] sort(int[] data) { | |
| if(data.length == 0) return new int[0]; | |
| int nBefore = 0; | |
| int nAfter = 0; | |
| int[] beforeArray = new int[data.length]; | |
| int[] afterArray = new int[data.length]; | |
| for(int i = 1; i < data.length; i++) { | |
| if(data[i] < data[0]) { | |
| beforeArray[nBefore++] = data[i]; | |
| } | |
| else { | |
| afterArray[nAfter++] = data[i]; | |
| } | |
| } | |
| int[] beforeArrayTrimmed = new int[nBefore]; | |
| int[] afterArrayTrimmed = new int[nAfter]; | |
| System.arraycopy(beforeArray, 0, beforeArrayTrimmed, 0, nBefore); | |
| System.arraycopy(afterArray, 0, afterArrayTrimmed, 0, nAfter); | |
| return concatArrays( | |
| concatArrays(sort(beforeArrayTrimmed), data[0]), | |
| sort(afterArrayTrimmed) | |
| ); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment