목록Timsort (1)

Little bIT awesome

Collections.sort에 쓰이는 TimSort

TimSort 창안자인 Tim Peters의 이름을 따서 팀 정렬(Tim sort) 알고리즘이라고 부른다. 처음 만들어졌을 때는 Python을 위해 C언어로 구현되었으나 현재 Java, Android, Google Chrome, swift 등에서 표준 정렬 알고리즘으로 채택되었다. 특징 '실제 데이터는 대부분 이미 정렬되어 있을 것이다.'라는 가정에 기반한 정렬 알고리즘 삽입정렬과 병합정렬을 적절히 조합한 알고리즘 현업에서 병합정렬, 퀵정렬보다 널리 쓰이는 정렬 알고리즘 현실세계의 데이터들이 완전 무작위로 배열돼 있기 보단 어느 정도 정렬된 상태로 배열돼 있는 경우가 많다면 정렬을 해야하는 전체 배열을 작은 덩어리들로 잘라 각각의 덩어리를 Insertion Sort로 정렬한 뒤 Merge Sort로 병합..
코딩테스트/알고리즘 정리 2024. 2. 2. 09:54
이전 Prev 1 Next 다음