Created
March 25, 2018 16:17
-
-
Save Dimanaux/5e0a11e711df4689d6d9c14845b72cf7 to your computer and use it in GitHub Desktop.
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
| import java.util.ArrayList; | |
| public class ArrayListAlgorithm { | |
| private static long iterations; | |
| public static long sort(ArrayList<Integer> array) { | |
| iterations = 0; | |
| quickSort(array, 0, array.size() - 1); | |
| return iterations; | |
| } | |
| private static void quickSort(ArrayList<Integer> array, int begin, int end) { | |
| if (begin < end) { | |
| int p = partition(array, begin, end); | |
| quickSort(array, begin, p - 1); | |
| quickSort(array, p + 1, end); | |
| } | |
| } | |
| private static int partition(ArrayList<Integer> array, int left, int right) { | |
| int pivot = array.get(left); | |
| swap(array, left, right); | |
| int store = left; | |
| for (int i = left; i < right; i++) { | |
| if (array.get(i) <= pivot) { | |
| swap(array, i, store); | |
| store++; | |
| } | |
| iterations++; | |
| } | |
| swap(array, right, store); | |
| return store; | |
| } | |
| private static void swap(ArrayList<Integer> array, int i, int j) { | |
| int tmp = array.get(i); | |
| array.set(i, array.get(j)); | |
| array.set(j, tmp); | |
| } | |
| } | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment