정렬 알고리즘인데 순서가 유지가 되어야 함
그런데 어차피 정렬할 대상은 인메모리에만 있고
프로그램이 꺼지고 재시작하면 0개 배열부터 다시 시작해도 됨
추가되는 항목은 한개씩만 있고 여러개씩 추가되지는 않음
알고리즘 잼병인데 대충 생각해보면
그냥 삽입 정렬로 추가될때마다 그 대상만 체크하면
어차피 매번 마다 복잡도는 o(n)일테니 그렇게해도 될 것 같기도 함
이 경우 o(n)보다 효율적인 정렬 알고리즘이 있을지 조언 바람
그런데 어차피 정렬할 대상은 인메모리에만 있고
프로그램이 꺼지고 재시작하면 0개 배열부터 다시 시작해도 됨
추가되는 항목은 한개씩만 있고 여러개씩 추가되지는 않음
알고리즘 잼병인데 대충 생각해보면
그냥 삽입 정렬로 추가될때마다 그 대상만 체크하면
어차피 매번 마다 복잡도는 o(n)일테니 그렇게해도 될 것 같기도 함
이 경우 o(n)보다 효율적인 정렬 알고리즘이 있을지 조언 바람
Introsort 그리고 삽입할때는 logN이면 충분하지 정렬된 데이터자너 - dc App
아 stable sort였네 어차피 매번 정렬하는거 아니고 켤때 한번만 정렬하는 거면 적당한 거 고르면 되지 않음? 기수정렬이 되는 케이스 제외하면 거기서거기일거같은데 - dc App
아 그렇쿤
근데 추가로 질문할게 정렬된 배열이 링크드 리스트인데 정렬된 링크드 리르트에서 효율적인 검색 알고리즘 추천 좀
뭔 ㅋㅋ 그딴거 없어
Head, tail에서부터 시작해서 동일한 element 찾는 식으로 중앙 찾아야될 것 같은데 이러면 o(logn)이 맞냐
doubly linked list 라면 가능하겠는데 singly linked list 면 o(n^2) 아니냐
더블 링크드 리스트임
아니 님 이제 보니 log n 찾고 있었네 그런 거 없어
merge sort 가 stable이고 n log n임
고전적인 링크드 리스트에서는 선형 검색 말고는 답이 없음 정 리스트에서 이진 검색을 하고 싶으면 스킵 리스트를 구현하던가 아니면 리스트를 포기하고 RB트리같은 이진 검색 트리로 짜는게 나음