검색을 쉽게 만드는 정렬 : 선택 정렬 vs 퀵 정렬
정렬(sorting)은 핵심적인 알고리즘 중 하나이다. 정렬은 항목을 순서대로 배열해서 검색이 빨리 실행될 수 있도록 도와준다.
이름을 알파벳순으로 정렬할때는 선택 정렬(selection sort)를 사용한다. 이렇게 불리는 까닭은 아직 정렬되지 않은 항목 중에서 다음 이름을 계속 선택하기 때문이다.
선택 정렬에는 많은 수의 작업이 들어간다. 이름을 훑어보는 횟수는 원래 항목의 수에 정비례 하게된다. 대략적으로는 N의 제곱이 걸린다.
다행히 떠 빨리 정렬하는 방법이 있다. 퀵정렬(quick sort)라는 방법으로, 영국인 컴퓨터과 학자인 토니 호어가 1959년경 고안했다. 이 알고리즘은 분할 정복의 훌륭한 사례다. 이 알고리즘은 선택 정렬에 비하면 작업의 수가 현저히 낮다.
(N x logN에 비례)
개발자 새싹🌱 The only constant is change.