Articles

정렬이란 무엇입니까?


우수 답변

컴퓨터 과학에서 정렬 알고리즘 은 목록의 요소를 특정 순서로 배치하는 알고리즘입니다. 가장 자주 사용되는 순서는 숫자 순서와 사전 순서입니다. 입력 데이터가 정렬 된 목록에 있어야하는 다른 알고리즘 (예 : 검색 및 병합 알고리즘)의 효율성을 최적화하려면 효율적인 정렬이 중요합니다. 정렬은 종종 데이터를 표준화하고 사람이 읽을 수있는 출력을 생성하는 데 유용합니다. 보다 공식적으로, 모든 정렬 알고리즘의 출력은 다음 두 가지 조건을 충족해야합니다.

  • 출력은 감소하지 않는 순서입니다 (각 요소는 원하는 총 순서에 따라 이전 요소보다 작지 않습니다).

    • li>
    • 출력은 입력의 순열 (재정렬이지만 원래 요소는 모두 유지)입니다.

    또한 입력 데이터는 종종 배열에 저장됩니다. 순차 액세스 만 허용하는 목록이 아닌 임의 액세스를 허용합니다. 여러 알고리즘이 적절한 수정 후 어느 유형의 데이터에도 적용될 수 있습니다.

    정렬 알고리즘은 종종 단어 뒤에 “정렬”이라는 단어가오고, 문법적으로는 영어에서 명사구로 사용됩니다. “큰 목록에서 삽입 정렬을 사용하는 것은 비효율적입니다.”라는 문장의 예에서 삽입 정렬은 삽입 정렬 알고리즘을 나타냅니다.

    Answer

    10 억 개의 개체를 정렬하는 것은 기억에 남을 수 있다면 확실히 도달 할 수 있습니다. O (n log n) 비교가 필요합니다. 컴퓨터 (또는 분산 시스템이있는 경우 컴퓨터)의 메모리에 맞는 항목을 정렬 할 수없는 경우 결과를 병합 정렬 할 수 있습니다. 1990 년대에 수정 된 병합 정렬이 세계 속도 기록을 세웠고 CPU 당 선형 속도가 빨라집니다.

    하지만 N이 커질 때 (또는 실제로 합리적인 입력을 위해 속도가 느려질 때마다) 실제로 필요한 것을 자세히 살펴 보는 것이 있습니다.

    객체를 정렬해야하는 이유는 무엇입니까? 복제물을 찾고 있다면 훨씬 더 빠른 방법이 있습니다! 아래쪽 (또는 위쪽) 5 \%를 처리하려면 포스트를 기준으로 분할 할 수있는 O (n) 알고리즘이 있습니다. 정렬 위치!

    물건이 느려질 때 무엇을하고 있는지 살펴보고 그것이 가장 빠른 알고리즘인지 알아 내기 전에 그게 옳은 일인지 알아 내야합니다. 전혀! (예외 : 더 빠른 “무엇이든”이 이미 디버깅 된 씬이라면 그냥 찰싹 때리기 만하면됩니다. 그렇게하는 것이 좋습니다… 배열에 몇 가지 요소가 여러 번 포함되어 있는지 테스트하는 것이 배열을 세트로 대체하는 것이 더 간단 할 수 있으며, 6 시간을 추가로 연구하면 절반을 제거 할 수 있다는 사실을 걱정하지 않아도됩니다. 수표 등).

답글 남기기

이메일 주소를 발행하지 않을 것입니다. 필수 항목은 *(으)로 표시합니다