fork(4) download 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.ArrayList;
  4. import java.util.Collections;
  5. import java.util.List;
  6.  
  7.  class QuickSort {
  8. 	public static void quicksort(List<Integer> list, int left, int right) {
  9. 		int q;
  10. 		if (right > left) {
  11. 			q = partition(list, left, right);
  12. 			// after ‘partition’
  13. 			// list[left..q-1] ≤ list[q] ≤ list[q+1..right]
  14. 			quicksort(list, left, q - 1);
  15. 			quicksort(list, q + 1, right);
  16. 		}
  17. 	}
  18.  
  19. 	static int partition(List<Integer> list, int left, int right) {
  20. 		int P = list.get(left);
  21. 		int i = left;
  22. 		int j = right + 1;
  23. 		for (;;) { // infinite for-loop, break to exit
  24. 			while (list.get(++i) < P)
  25. 				if (i >= right)
  26. 					break;
  27. 			// Now, list[i]≥P
  28. 			while (list.get(--j) > P)
  29. 				if (j <= left)
  30. 					break;
  31. 			// Now, list[j]≤P
  32. 			if (i >= j)
  33. 				break; // break the for-loop
  34. 			else
  35. 				// swap(list[i],list[j]);
  36. 				Collections.swap(list, i, j);
  37. 		}
  38. 		if (j == left)
  39. 			return j;
  40. 		// swap (list[left],list[j]);
  41. 		Collections.swap(list, left, j);
  42. 		return j;
  43. 	}
  44.  
  45. 	public static void main(String[] args) {
  46. 		List<Integer> list = new ArrayList<Integer>();
  47. 		list.add(1);
  48. 		list.add(2);
  49. 		list.add(3);
  50. 		list.add(-1);
  51. 		list.add(4);
  52. 		quicksort(list, 0, 4);
  53. 		for (int i = 0; i < list.size(); i++) {
  54. 			System.out.println(list.get(i));
  55. 		}
  56. 	}
  57. }
Success #stdin #stdout 0.09s 320320KB
comments (?)
stdin 
Standard input is empty
stdout 
-1
1
2
3
4
https://ideone.com/RCAKI8
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!