이진검색을 사용하려면 애초에 먼저 이름을 알파벳순으로 정렬을 해야한다.
이진검색으로 효율적으로 찾을 수 있도록 사전에 이름을 알파벳순으로 정렬하고 싶다고 가정해 보자 먼저 살펴볼 알고리즘은 선택 정렬이다. 이렇게 불리는 까닭은 아직 정렬되지 않은 항목중에서 다음 이름을 계속 선택하기 때문이다. 앞선 키 큰 사람 찾는 기법에 바탕을 두고 있다.
10명의 이름이 있다고 가정했을때, 1번과2번을 비교하고 먼저인사람과 3번을 비교하고 다시 4번과 비교하고...
반복해서 한명을 추려낸 뒤 남은 9명을 똑같이 반복하고 그다음 8 명 ... 반복해서
정렬을 한다. 이수열의 합계는 n * (n+1)/2가 되고 2로나누는걸 무시하면 일의 양은 n^2+n에 비례한다.
반면에 퀵 정렬은
10명의 그룹 중에서 a부터 m까지인 이름을 한그룹으로 모으고 n에서 z까지인 이름을 다른 그룹으로 모은다.
이렇게 하면 그룹이 두 개 생기고 각가에 절반 정도의 이름이 들어가 있다. 이제 a-f까지, g부터 m까지의 그룹으로 나누고
반대 그룹도 똑같이 반으로 나눈다.
이러한 방식으로 작업 하면 n개의 항목을 정렬하려면 n*logn 에 비례한다.
>_<