저의 동료들은 오늘 아침 정렬 알고리즘에 대한 토론으로 제 대학 시절로 시간을 되돌 렸습니다. 우리는 StupidSort 와 같은 즐겨 찾기를 연상 시켰으며 , 우리 중 한 명이 정렬 알고리즘을 보았을 것이라고 확신했다 O(n!). 그것은 내가 찾을 수있는 “가장 최악의”정렬 알고리즘을 찾기 시작했다.
(- 아니 RANDOMIZE 다시는 순서에? 즉 RANDOMIZE 요소), 나는 주위를 둘러 보았다 그리고 그것은 분명히라고 사실을 발견 우리는 완전히 임의의 종류가 아주 나쁜 될 것이라고 가정 보고 정렬, 또는 원숭이를 정렬하거나, 때로는 랜덤 정렬 .
Monkey Sort는 최악의 성능 O(∞), 최상의 성능 O(n)및 평균 성능 을 가진 것으로 보입니다 O(n·n!).
최악의 평균 정렬 성능을 가진 현재 공식적으로 허용되는 정렬 알고리즘은 무엇입니까 O(n·n!)?
답변
에서 데이비드 모건-월 의 비전 알고리즘 페이지 : 지적 설계 정렬
소개
지능형 디자인 정렬은 지능형 디자인 이론을 기반으로 한 정렬 알고리즘입니다.
알고리즘 설명
원래 입력 목록이 정확한 순서로있을 확률은 1 / (n!)입니다. 이런 일이 우연히 일어났다 고 말할 수는 없을 정도로 작은 가능성이 있기 때문에, 그것은 지능적으로 분류기에 의해 의식적으로 그 순서대로 놓여져 있어야합니다. 따라서 “오름차순”에 대한 순진한 필사자의 이해를 초월하는 방식으로 이미 최적으로 정렬되어 있다고 가정하는 것이 안전합니다. 우리 자신의 선입견을 따르기 위해 그 순서를 바꾸려고하면 실제로는 덜 분류 될 것입니다.
분석
이 알고리즘은 시간이 일정하며 추가 메모리가 필요하지 않고 목록을 적절하게 정렬합니다. 사실, 그것은 의심스러운 기술적 인 컴퓨터를 필요로하지 않습니다. 분류기를 찬양하라!
피드백
게리 로저스의 글을 참고하세요 :
정렬 시간을 일정하게 설정하면 분류기의 성능이 거부됩니다. 분류기는 시간이 지남에 따라 정렬되므로 시간이 없습니다. 정렬을 확인하는 데 시간이 걸리면 정렬 기의 역할이 어려워집니다. 따라서 …이 특정 종류는 결함이 있으며 ‘The Sorter’에 기인 할 수 없습니다.
이교!
답변
몇 년 전, 나는 MiracleSort를 발명했지만 (실제로는 구현하지는 않았습니다).
Start with an array in memory.
loop:
Check to see whether it's sorted.
Yes? We're done.
No? Wait a while and check again.
end loop
결국, 메모리 칩에서 비트를 뒤집는 알파 입자는 성공적으로 정렬되어야합니다.
안정성을 높이려면 어레이를 차폐 위치에 복사하고 잠재적으로 정렬 된 어레이를 원본과 비교하십시오.
그렇다면 잠재적으로 정렬 된 배열을 원본과 어떻게 비교합니까? 각 배열을 정렬하고 일치하는지 확인하십시오. MiracleSort는이 단계에서 사용할 확실한 알고리즘입니다.
편집 : 엄밀히 말하면, 이것은 종료가 보장되지 않기 때문에 알고리즘이 아닙니다. “알고리즘이 아닌”이 “나쁜 알고리즘”으로 인정됩니까?
답변
양자 역학에 대한 많은 세계 해석이 정확하다고 가정하는 정렬 알고리즘 :
- 목록이 정렬되어 있는지 확인하십시오. 그렇지 않다면 우주를 파괴하십시오.
알고리즘의 결론에 따라, 목록은 유일하게 남아있는 유일한 우주에서 정렬됩니다. 이 알고리즘은 최악의 경우 O (N) 및 평균의 경우 O (1) 시간이 걸립니다. 실제로 수행되는 평균 비교 수는 2입니다. 두 번째 요소에서 우주가 파괴 될 확률은 50 %이고 세 번째 요소에서 우주가 파괴 될 확률은 25 %입니다.
답변
아직 아무도 sleepsort를 언급하지 않은 것에 대해 놀랐습니다 … 또는 눈치 채지 못했습니까? 어쨌든:
#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
f "$1" &
shift
done
wait
사용법 예 :
./sleepsort.sh 5 3 6 3 6 3 1 4 7
./sleepsort.sh 8864569 7
성능면에서 끔찍합니다 (특히 두 번째 예). 거의 3.5 개월을 기다려서 2 개의 숫자를 정렬하는 것은 다소 나쁘다.
답변
여기에 설명 된대로 징글 정렬 .
당신은 당신의 목록에있는 각 가치를 크리스마스에 다른 어린이에게줍니다. 끔찍한 인간 인 아이들은 선물의 가치를 비교하고 그에 따라 분류합니다.
답변
한 번 무작위 배열 생성을 제안한 강사가 정렬되어 있는지 확인한 다음 정렬 할 배열과 데이터가 동일한 지 확인했습니다.
최고의 사례 O (N) (처음으로 베이비!) 최악의 경우 O (Never)
답변
알고리즘을 어떤 식 으로든 의미있게 유지한다면 O(n!)달성 할 수있는 최악의 상한입니다.
집합의 순열을 정렬 할 수있는 가능성을 확인 n!하면 단계가 수행되므로 그보다 더 나빠질 수는 없습니다.
그보다 더 많은 단계를 수행하면 알고리즘에 유용한 목적이 없습니다. 다음과 같은 간단한 정렬 알고리즘은 말할 것도 없습니다 O(infinity).
list = someList
while (list not sorted):
doNothing
