Advertisement
Guest User

quicksort ultraaaaaaaa

a guest
Nov 19th, 2019
127
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.28 KB | None | 0 0
  1. public class ListTest {
  2. private final int SIZE = 10;
  3. int v1,v2;
  4. public ListTest(){
  5. List<Integer> l = new List<Integer>();
  6. for (int i=1;i<=SIZE ;i++ ) {
  7. l.append((int)(Math.random()*10000));
  8.  
  9. }
  10. l.toFirst();
  11. for (int a = 0;a<SIZE ;a++ ) {
  12. System.out.println(a+ ": "+l.getContent());
  13. l.next();
  14. } // end of for
  15. qsort(l,0,SIZE-1);
  16. System.out.println("---------------------------------");
  17. l.toFirst();
  18. for (int a = 0;a<SIZE ;a++ ) {
  19. System.out.println(a+ ": "+l.getContent());
  20. l.next();
  21. } // end of for
  22. }
  23.  
  24. public void qsort(List<Integer> F, int u, int o){
  25. int l = u, r = o;
  26. if (o>u) {
  27. //int p = F[(u+o)/2];
  28. int p = findP(F,u,o);
  29.  
  30. while (l <= r) {
  31. //while (l<o && F[l]<p)++l;
  32. //while (r> u && F[r]>p) --r;
  33. while (l<o && findFl(F,l)<p)++l;
  34. while (r> u && findFr(F,r)>p) --r;
  35. if (l<=r) {
  36. swap(F,l,r);
  37. ++l;
  38. --r;
  39. } // end of if
  40. } // end of while
  41. if (u<r) qsort(F,u,r);
  42. if (l<o) qsort(F,l,o);
  43. } // end of if
  44.  
  45.  
  46. }
  47.  
  48.  
  49. public int findP(List<Integer> l,int u,int o){
  50. int pZ = (u+o)/2;
  51. int pP = 0;
  52. l.toFirst();
  53. for (int a = 0;a<pZ ;a++ ) {
  54. pP = l.getContent();
  55. l.next();
  56. } // end of for
  57. return pP;
  58.  
  59. }
  60.  
  61. public int findFl(List<Integer> f,int l){
  62. int pL = 0;
  63. f.toFirst();
  64. for (int a = 0;a<l ;a++ ) {
  65. pL = f.getContent();
  66. f.next();
  67. } // end of for
  68. return pL;
  69.  
  70. }
  71.  
  72.  
  73. public int findFr(List<Integer> f,int r){
  74. int pR = 0;
  75. f.toFirst();
  76. for (int a = 0;a<r ;a++ ) {
  77. pR = f.getContent();
  78. f.next();
  79. } // end of for
  80. return pR;
  81.  
  82. }
  83.  
  84. public void swap(List<Integer> F, int l, int r ){
  85. int sR = findFr(F,r);
  86. int sL = findFl(F,l);
  87. F.toFirst();
  88. for (int a = 0;a<r-1 ;a++ ) {
  89. F.next();
  90. } // end of for
  91. F.setContent(sL);
  92.  
  93. F.toFirst();
  94. for (int a = 0;a<l-1 ;a++ ) {
  95. F.next();
  96. } // end of for
  97. F.setContent(sR);
  98.  
  99. }
  100.  
  101.  
  102.  
  103. public static void main(String[] args) {
  104. new ListTest();
  105. }
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement