따라서 기본적으로 다음과 비슷한 비교 함수가 제공되면 평균 경우에서 저하되지 않는 정렬 알고리즘이 있는지 알고 싶습니다.

int Compare(object a, object b) { return Random.Next(-1,1); }

… 여기서 Random.Next ()는 지정된 포괄적 인 하한과 상한 사이에서 무작위로 생성 된 정수를 생성하는 메소드입니다.

실제로 대부분의 기본 정렬 알고리즘은 다음 두 가지 조건 중 하나 이상을 준수하기 때문에 평균 사례에 따라 수행됩니다.

1. 두 가지 고유 한 요소 간의 비교는 결코 두 번이나 이루어지지 않습니다.
2. 정렬의 각 반복에서 적어도 하나의 요소의 올바른 위치가 결정되어 요소가 다시 비교되지 않습니다.

예를 들어, SelectionSort는 정렬되지 않은 요소의 하위 목록을 반복하고 “가장 작은”및 / 또는 “가장 큰”요소를 찾은 다음 (각 요소를 지금까지 가장 큰 요소와 비교하여) 올바른 위치에 놓고 반복합니다. 결과적으로 결정적이지 않은 비교기조차도 모든 반복이 끝날 때마다 알고리즘은 최소 또는 최대라고 생각하는 값을 찾은 다음 결정하려고하는 위치의 요소와 교체하며 결코 고려하지 않습니다. 그러나이 프로세스 동안 A와 B를 여러 번 비교할 수 있습니다 (가장 극단적 인 예로, 역순으로 정렬 된 배열에서 SelectionSort의 여러 패스를 고려하여 조건 1을 위반 함). .

MergeSort는 조건 1에 따르지만 2에는 맞지 않습니다. 하위 배열이 병합 될 때 동일한 하위 배열 (왼쪽 또는 오른쪽)의 요소는 배열의 해당 요소가 순서대로 정렬 된 것으로 이미 결정 되었기 때문에 서로 비교되지 않습니다. 이 알고리즘은 각 하위 배열의 병합되지 않은 요소 중 가장 적은 요소 만 다른 요소와 비교하여 병합 된 목록에서 다음 중 더 적은 요소를 결정합니다. 즉, 두 개의 고유 한 객체 A와 B가 서로 최대 한 번 비교되지만 전체 컬렉션에서 지정된 요소의 “최종”인덱스는 알고리즘이 완료 될 때까지 알 수 없습니다.

InsertionSort는 전반적인 전략과 복잡성이 SelectionSort와 비슷해 보이지만 Condition 1 만 준수합니다. 정렬되지 않은 각 요소는 검사중인 요소보다 작은 요소가 발견 될 때까지 가장 먼저 정렬 된 요소와 비교됩니다. 해당 시점에 요소가 삽입 된 후 다음 요소가 고려됩니다. 결과적으로 A와 B의 상대 순서는 한 번의 비교로 결정되며 A와 B 사이의 추가 비교는 수행되지 않지만 모든 요소가 고려 될 때까지 요소의 최종 위치를 알 수 없습니다.

QuickSort는 두 가지 모두를 준수 합니다정황. 각각의 레벨에서, “왼쪽”측이 피봇보다 작은 요소를 포함하고 “오른쪽”측이 피봇보다 큰 요소를 포함하도록 피봇이 선택되고 배열된다. 해당 레벨의 결과는 QuickSort (왼쪽) + 피벗 + QuickSort (오른쪽)이며 기본적으로 피벗 요소의 위치가 알려져 있음을 의미합니다 (왼쪽의 길이보다 하나의 색인이 더 크다). 피벗은 다른 요소와 비교되지 않습니다. 피벗으로 선택된 후 (이전 피벗 요소와 비교되었을 수 있지만 해당 요소는 알려진 것으로 하위 배열에 포함되지 않음) 피벗의 반대쪽에있는 A 및 B는 절대로 비교했다. 순수한 QuickSort의 대부분의 구현에서 기본 사례는 하나의 요소이며,이 시점에서 현재 색인은 최종 색인이며 더 이상 비교되지 않습니다.

내가 생각할 수있는 유일한 비교 종류는 최적화되지 않은 BubbleSort입니다. 정렬이 X 패스를 실행 한 후 X 가장 큰 요소가 올바른 위치에 있음을 승인하지 않거나 “더블 체크”패스를 사용하여 목록이 정렬되었는지 확인하는 경우 정렬은 “완료”로 간주됩니다. 임의의 비교가 더 교환이 수행되지 않음 따라서 모든 인접한 두 패스 동안 목록의 요소 (진정한 랜덤 경우, 확률로 발생할 수있는 이벤트를 리턴 -1 또는 0했다 , 비교적 대해 25 개 요소의 작은 목록 (2000 개 확률 중 하나), 100 개 요소의 경우 확률은 3.7 * 10 ^-18(2/3)N−1

$(2/3)^{N-1}$). 비교기 결과의 최대 절대 값이 증가함에 따라 하나의 비교에서 음수 또는 0을 반환 할 확률이 0.5로 감소하여 알고리즘을 종료 할 가능성이 훨씬 낮아집니다 (99 코인이 모든 착륙 헤드를 뒤집을 가능성) 어느는이 귀결 무엇 기본적 1 1.2 * 10 ³⁰ )

오랜 시간 편집 : 무작위 비교기를 포함하지 말아야 할 일의 예로 특별히 설계된 몇 가지 “정렬”이 있습니다. 아마도 가장 유명한 것은 BogoSort 일 것입니다. “목록이 제공되면 목록이 순서가 맞지 않으면 목록을 섞고 다시 확인하십시오.” 이론적으로는됩니다 결국 바로 위의 “최적화되지 않은 거품 정렬”같은 값의 오른쪽 순열에 맞았지만 평균의 경우는 충분히 무작위 순열 후 (N! / 2), 때문에 생일 문제의 계승 시간 (당신 고유 한 것보다 중복 순열이 발생할 가능성이 높아집니다.

답변

insert x [] = [x]
insert x y:ys = if x < y then x:y:ys
                else y:insert x ys

sort_aux l e = match l with
                 [] -> e
                 x:xs -> sort_aux xs (insert x ys)

sort l = sort_aux l []

module Main where

import Control.Monad
import Data.Map (Map)
import qualified Data.Map as Map
import System.Random (randomIO)

--------------------------------------------------------------------------------

main :: IO ()
main = do
  let xs = [0..9]
  xss <- replicateM 100000 (msortRand xs)
  print $ countFrequencies xss

msortRand :: [a] -> IO [a]
msortRand = msort (\_ _ -> randomIO)

countFrequencies :: (Ord a) => [[a]] -> [Map a Int]
countFrequencies [] = []
countFrequencies xss = foldr (\k m -> Map.insertWith (+) k 1 m) Map.empty ys : countFrequencies wss
  where
    ys = map head xss
    zss = map tail xss
    wss = if head zss == []
      then []
      else zss

--------------------------------------------------------------------------------

msort :: (Monad m) => (a -> a -> m Bool) -> [a] -> m [a]
msort (<) [] = return []
msort (<) [x] = return [x]
msort (<) xs = do
  ys' <- msort (<) ys
  zs' <- msort (<) zs
  merge (<) ys' zs'
  where
    (ys, zs) = split xs

merge :: (Monad m) => (a -> a -> m Bool) -> [a] -> [a] -> m [a]
merge (<) [] ys = return ys
merge (<) xs [] = return xs
merge (<) (x:xs) (y:ys) = do
  bool <- x < y
  if bool
    then liftM (x:) $ merge (<) xs (y:ys)
        else liftM (y:) $ merge (<) (x:xs) ys

split :: [a] -> ([a], [a])
split [] = ([], [])
split [x] = ([x], [])
split (x:y:zs) = (x:xs, y:ys)
  where
    (xs, ys) = split zs