-4
나는이 다음 정렬 알고리즘 : 온라인 또는 오프라인 종류입니다 그들 중온라인 및 오프라인 정렬 알고리즘을 구분하는 방법은 무엇입니까?
Bubble Sort, Selection Sort, Heap Sort, Merge Sort, Quick Sort, Insertion Sort
? 미리 감사드립니다.
A
답변
1
"온라인"정렬 알고리즘을 정의하는 방법에 따라 다릅니다. 당신이 사용하는 경우 Wikipedia definition :
컴퓨터 과학에서, 온라인 알고리즘이 처리 할 수있는 일이 그 입력 조각별로 조각 입력이 공급되는 순서대로 직렬 방식으로, 즉, 전체 입력을 시작하지 않고도 을 사용할 필요없이 알고리즘에 적용 할 수 있습니다.
목록에있는 알고리즘 중 삽입 정렬만으로 청구서에 맞 춥니 다. 다른 정렬에서는 정렬이 시작되기 전에 모든 항목이 메모리에 있어야하기 때문입니다.
삽입 정렬을 사용하면 정렬 된 목록을 유지 관리 할 수 있습니다. 각 항목은 수신 할 때 올바른 위치에 저장됩니다. 지금까지받은 항목 목록은 항상 순서대로 표시됩니다.
는 참조 https://cs.stackexchange.com/questions/55012/what-is-the-fastest-online-sorting-algorithm
한 번에 하나 개의 요소를 가져 오는 동안 종류도 힙 분 힙을 유지 할 수 없습니다? – rcgldr
@rcgldr 예, 힙을 유지 관리 할 수 있습니다. 그러나 마지막 요소가 수신 된 후에는 힙에서 항목을 한 번에 하나씩 제거하거나 힙을 다시 정렬하여 항목을 정렬해야합니다. 어느 쪽이든, 당신은 그것을하기 전에 메모리에있는 모든 항목을 가지고 있어야하며, 그 단계를 수행하는 데 O (n log n) 시간이 필요합니다. –