Sort
Sorting이란 무언가를 정리하는 것을 의미하며, 사전처럼 A부터 Z까지 기준으로 정렬하든가 큰 수에서 작은 수 기준으로 정렬할 수 있다.
이진검색 알고리즘을 사용하기 위해서는 배열을 정렬해야 한다.
아래의 버블정렬, 선택정렬, 삽입정렬은 실제로 자주 쓰이는 알고리즘은 아니지만 이해가 가장 쉽기 때문에 먼저 살펴본다!
Bubble Sort (버블정렬)
배열 내 아이템 두 개를 선택해서 비교를 한다.
왼쪽이 오른쪽보다 크면 둘을 바꾼다.
오른쪽이 왼쪽보다 크면 바꾸지 않고 오른쪽으로 이동해서 해당 프로세스를 반복한다.
해당 사이클이 끝나고 나면 다시 처음부터 반복한다.
버블정렬 시간복잡도
버블정렬의 시간복잡도는 O()이다.
Selection Sort (선택정렬)
배열 내 전체 아이템 중 가장 작은 아이템(처음엔 0인덱스 아이템)의 위치를 변수에 저장한다.
오른쪽으로 가면서 더 작은 숫자가 나올 경우 해당 위치를 변수에 저장한다. 해당 사이클이 끝나고 나면 가장 작은 숫자의 위치와 첫 번째 아이템 (0인덱스 아이템)의 위치를 바꾼다. 즉, 한 사이클에 한 번의 교체만 일어난다.
다음 사이클에서는 정렬된 숫자를 제외하고 똑같은 프로세스를 실행한다.
선택정렬 시간복잡도
선택 정렬이 버블 정렬보다 더 빠르게 실행될 수 있음에도 불구하고, 선택 정렬의 시간 복잡도도 버블 정렬과 똑같이 O()이다.
Insertion Sort (삽입정렬)
인덱스 1의 아이템이 왼쪽 아이템보다 큰지 비교한 후 왼쪽 아이템이 클 경우 인덱스 1의 아이템이 왼쪽으로 이동하면서 첫 번째 사이클이 끝난다.
두 번째 사이클에서는 인덱스 2의 아이템이 왼쪽 아이템보다 큰지 비교하면서 똑같은 프로세스를 진행한다. 만약 왼쪽 아이템이 클 경우 왼쪽 아이템과 위치가 바뀌고, 바뀐 위치에서 왼쪽 아이템과 다시 크기 비교를 한다. 인덱스 0까지 비교를 한 후 왼쪽 아이템이 크지 않으면 해당 사이클은 종료된다.
삽입정렬 시간복잡도
삽입정렬은 필요한 아이템만 스캔하기 때문에 선택정렬보다 빠르다.
그러나, 삽입정렬의 시간복잡도는 선택정렬, 버블정렬 시간복잡도와 동일하게 O()이다.
정렬 알고리즘의 시간복잡도
버블정렬, 선택정렬, 삽입정렬의 시간복잡도가 동일한 이유는 최악의 시나리오가 아닌 평균 시나리오에 따라 측정되기 때문이다.
따라서 삽입, 선택 정렬은 작은 DB 기준으로는 훌륭한 알고리즘이지만 데이터가 커지면 커질수록 느려질 수 있다.
