Geek asks and answers

Can List.Sort use a randomized comparison delegate endlessly?

I study and test the performance of various randomization methods for ordered collections, and I considered passing a Comparison delegate, which simply randomly returns a comparison result. For instance:

int RandomComparison<T> (T x, T y)
{
    return this.random.Next (-1, 2);
}

However, since I don’t know the sorting algorithm used under the hood, I don’t know if this could lead to the sorting logic never ending. Although this method seems generally unreliable in performance, I wonder if it is unsuitable for use?

+3
source share
6 answers

List.Sort QuickSort ( ), ...

, 1 , N N . , .

, ( ), (O (n log n) , , O ( n ^ 2) ), "", . , , .

, , . , . , , , , , , . QuickSort, , - , , , - - , - . , "" , , , , .

, , , "" . , , n , , . 2^n ( , List.Sort, , , , ). , , - "" , , "".

, , . , , QuickSort , . (, , , ), , , 1 2 ^ (n-1 ) ( , ), - 1 n. , "" .

+3

: ,

+4

, . , , , A < B B < C, A < .

, .

+4

, , . .

Fisher-Yates shuffle. O (n), , .

+2

, . ...

.

, , :

:

procedure bubbleSort( A : list of sortable items )
  do
    swapped = false
    for each i in 1 to length(A) - 1 inclusive do:
      if A[i-1] > A[i] then
        swap( A[i-1], A[i] )
        swapped = true
      end if
    end for
  while swapped
end procedure

, .

, (quicksort, mergesort, heapsort, insertionsort), for, . , (. wiki )

So, from a practical point of view, the no: . The correctness of the comparison function should not affect the behavior during sorting *

* modulo things like quicksort, O (n ^ 2) in the worst case ...

+1
source

Once you pass the sort procedure to a function that does not give a sequential order, there is no guarantee what will happen. One would hope that C # does nothing bad, but I know from experience that C ++ has an alarming tendency to drop the kernel in this situation.

0
source

More articles:


All Articles