Đây có phải là QuickSort không?

Question

Tôi đang cố gắng viết một quicksort cho sự chỉnh sửa của riêng tôi. Tôi đang sử dụng pseudocode on wikipedia làm hướng dẫn. Mã của tôi hoạt động. Có vẻ như nó sẽ chạy trong thời gian O (n log n). Tôi đã thử thực sự định thời gian mã của mình để kiểm tra độ phức tạp (tức là, khi tôi tăng gấp đôi kích thước đầu vào, thời gian chạy có tăng khoảng n log n), nhưng tôi vẫn không chắc chắn.

Mã của tôi có vẻ khá đơn giản. Tôi thực hiện sắp xếp tại chỗ. Các triển khai khác mà tôi đã thấy sử dụng một hàm phân vùng, mà tôi không có. Điều này làm cho tôi nghĩ rằng tôi đã thực hiện một số thuật toán sắp xếp khác. Đây có phải là thuật toán quicksort không?

public static void QuickSortInPlace(int[] arr) 
{ 
    QuickSortInPlace(arr, 0, arr.Length - 1); 
} 

private static void QuickSortInPlace(int[] arr, int left, int right) 
{ 
    if (left < right) 
    { 
     //move the middle int to the beginning and use it as the pivot 
     Swap(arr, left, (left + right)/2); 

     int pivotIndex = left; 
     int pivot = arr[pivotIndex]; 
     int min = left + 1; 
     int max = right; 

     for (int i = min; i <= max; i++) 
     { 
      if (arr[i] > pivot) 
      { 
       Swap(arr, i, max); 
       max--; //no longer need to inspect ints that have been swapped to the end 
       i--; //reset the loop counter to inspect the new int at the swapped position 
      } 
     } 

     //move pivot to its sorted position 
     Swap(arr, max, pivotIndex); 

     //recurse on the sub-arrays to the left and right of the pivot 
     QuickSortInPlace(arr, left, max - 1); 
     QuickSortInPlace(arr, max + 1, right); 
    } 
} 

Phiên bản thứ hai dựa trên phản hồi của Dukeling.

public static void QuickSortInPlace3(int[] arr, int min, int max) 
{ 
    if (min < max) 
    { 
     int pivotIndex = min; 
     int pivot = arr[pivotIndex]; 

     int left = min; 
     int right = max; 

     while (left <= right) 
     { 
      while (arr[left] < pivot) 
       left++; 

      while (arr[right] > pivot) 
       right--; 

      if (left <= right) 
      { 
       Swap(arr, left, right); 
       left++; 
       right--; 
      } 
     } 

     QuickSortInPlace3(arr, min, right); 
     QuickSortInPlace3(arr, left, max); 
    } 
} 

Answer 1

Có, nó chắc chắn đủ gần để phân loại nhanh như vậy hoặc ít nhất là một biến thể nhỏ.

Bạn đang phân vùng dữ liệu, bạn chỉ không có chức năng riêng cho nó.

Bạn có điều gì đó hơi lạ xảy ra.

Thông thường, với biến thể tại chỗ của quicksort, bạn tăng chỉ mục bên trái trong khi nó nhỏ hơn trục, sau đó bạn giảm chỉ mục bên phải trong khi lớn hơn, sau đó bạn trao đổi hai (chỉ thực hiện hoán đổi liên quan đến 2 các yếu tố cả ở bên trái).

Tuy nhiên, bạn chỉ cần tăng bên trái, vì vậy bạn có thể trao đổi các phần tử đã lớn hơn từ bên phải. Điều này có thể dẫn đến một vài hoán đổi nhiều hơn mức cần thiết, mặc dù thời gian chạy tiệm cận nên giống nhau.

Dưới đây là một số giả của các biến thể 'bình thường'. (Lấy từ Rosetta Code)

while left ≤ right 
    while array[left] < pivot 
     left := left + 1 
    while array[right] > pivot 
     right := right - 1 
    if left ≤ right 
     swap array[left] with array[right] 
     left := left + 1 
     right := right - 1