Tim sort 알고리즘

• 가장 효율적이라고 꼽히는 알고리즘
• Collection.sort()와 함께 Arrays.sort() 라이브러리가 이 알고리즘을 사용하고 있음
  • 대신 Arrays.sort()는 Arrays.sort(int[] a)와 Arrays.sort(Object[] o)처럼 원시형과 래퍼형을 받는 두 가지 메서드가 있는데, 래퍼형을 받는 메서드가 Tim sort 알고리즘을 사용하고 있어서 더 효율적임.
  • Collection.sort()는 내부적으로 Arrays.sort(Object[] o)를 사용하고 있음(Tim sort)

public class StoreSorter {

    public List<Store> sortByRate(List<Store> stores){

        stores.sort(Comparator.comparingDouble(Store::getRate).reversed());
        return stores;
    }
}

//현재는 내림차순으로 반환하기 위해서 revered()를 추가적으로 사용함.

@Test
    void test2(){

        ArrayList<Long> id = new ArrayList<>();
        for(Long i =4000L; i<5000L; i++){
            id.add(i);
        }

        StoreSorter storeSorter = new StoreSorter();

        List<Store> storeList = storeRepository.findAllById(id);
        List<Store> stores = storeSorter.sortByRate(storeList);

        for(int i =0; i<stores.size()-1; i++) {
            assertThat(stores.get(i).getRate() >= stores.get(i+1).getRate()).isTrue();
        }
    }
    
    테스트+디버깅으로 실제로 평점에 의해서 내림차순이 됐는지 확인함

시간 비교

Tim sort 알고리즘

1) 데이터 1000건

1회 -0.128821 초

2회 -0.007초