BetinaUKTC

paste

Jan 14th, 2021 (edited)
609
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package QickSort;
  2.  
  3. public class QuickSort_Methods {
  4.  
  5.     public static int Partition(int[] arr, int low, int high) {
  6.         // слагаме първи елемент като пивот
  7.         int pivot = arr[low];
  8.         //индекс, който ще пази правилното място на пивот елемента
  9.         int i = low + 1;
  10.  
  11.         for (int j = low + 1; j <= high; j++) {
  12.             if (arr[j] < pivot) {
  13.                 /*преподреждаме масива, като всички по-малки ги
  14.                 слагаме преди пивот елемнта, а по-големите след него
  15.                  */
  16.                 int buff = arr[i];
  17.                 arr[i] = arr[j];
  18.                 arr[j] = buff;
  19.                 i++;
  20.             }
  21.         }
  22.  
  23.         //слагаме пивот елемента на правилното му място
  24.         int buff = arr[low];
  25.         arr[low] = arr[i - 1];
  26.         arr[i - 1] = buff;
  27.  
  28.         //връщаме индекса на пивот елемента
  29.         return i - 1;
  30.     }
  31.  
  32.     public static void QuickSort(int[] arr, int low, int high) {
  33.         if (low < high) {  // дъно на рекурсията
  34.  
  35.  
  36.             int pivotIndex = Partition(arr, low, high);
  37.  
  38.             //сортираме лявата част на масива (елементите преди пивот)
  39.             QuickSort(arr, low, pivotIndex - 1);
  40.  
  41.             //сортираме дясната част на масива (елементите след пивот)
  42.             QuickSort(arr, pivotIndex + 1, high);
  43.         }
  44.     }
  45. }
  46.  
  47.  
  48.  
RAW Paste Data