[일반] 정렬 초보 질문좀

[익명(14.37)]

n개의 입력을 받아 크기 순서대로 정렬해야할때

1. 그때그때 정렬

2. 먼저 다 받은다음에 한번에 정렬

1번이 더 빠르지?

1 + log2 + ... + logn < nlogn 이니까

맞음?

[익명(112.186)]

1 + log2 + ... + log이 아니라 1log1 + 2log2 + ... +nlogn 인데요

[익명(14.37)]

왜? 이미 정렬되어있는 곳에 꽂아넣는거니까 이분탐색으로 log n 아니야?

[익명(112.186)]

그렇게 하려면 힙이랑 트리 써야함. 선형 자료구조에는 어떻게 되겠음?

[익명(121.185)]

이진탐색이라 치면 인덱스 접근과 임의 위치에 삽입이 둘 다 O(1)에 되지 않음

[익명(14.37)]

감사합니다 형님 배워가요

[익명(121.185)]

1은 BBST고 1 2 차이도 어차피 상수배라 실제 수행 시간으로 보면 2가 무조건 빠를듯?

[익명(49.167)]

선형 자료구조는 1에서 정렬을 N번하잖아

[익명(121.182)]

만약 n개의 입력을 받아 크기 순서대로 정렬해야하지만 그 입력은 총 m개의 서로 다른 섹션으로 구분되어 그 이전 섹션의 모든 값이 이후 섹션의 모든 값보다 낮으면, 각 섹션을 독자적으로 정렬한 다음 하나로 합치는게 다 받아 한 번 정렬하는 것보다 빠르겠죠. 하지만 그냥 입력을 받을 때마다 같은 컨테이너를 매번 정렬하는거라면 그냥 마지막에 한 번만 하는게 낫습니다.

[익명(121.182)]

n개의 입력 중 t개의 입력을 이미 받아 정렬했다 해도, 그 이후 오는 입력이 이미 정렬한 입력에 비해 그 위치가 어떻게 될지 추측할 수 있는 정보가 없다면 매번 올바른 인덱스의 위치를 다시 찾아 삽입해야겠죠.

[익명(14.37)]

ㄳㄳ

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(14.37)]

그렇구나 ㄳㄳ