[뇌를 자극하는 알고리즘] 5. 정렬

알고리즘(Algorithms): 문제를 해결하기 위한 일련의 명령이나 반복되는 절차
정렬 알고리즘: 데이터를 가지런히 나열하는 그 자체가 목적이 아니라 찾고자 하는 데이터를 빠르고 쉽게 찾을 수 있게 하는 것이 목적.

5.2 버블 정렬

버블정렬(Bubble Sort): 데이터 집합을 순회하면서 집합 내의 이웃 요소들끼리의 교환을 통해 정렬을 수행
ex)오름차순(왼<오): 제일 왼쪽에 있는 요소부터 이웃 요소의 데이터와 비교해 나가며 교환을 수행. 제일 큰 수부터 순서대로 원하는 위치(마지막)에 가면 그 요소는 제외하고 정렬을 계속함.

 

-버블 정렬 반복 횟수:한번 순회할 때(가장 큰 값이 가장 위에 놓여 제외할 때)마다 정렬해야 하는 데이터의 집합 번위가 하나씩 줄어들므로, 데이터 집합의 범위를 n개면 n-1만큼 반복하면 정렬이 마무리됨. 이 책의 예제에서는 데이터 집합의 범위가 6개이니 5회 반복.

-버블 정렬 비교 횟수:5회를 반복하는데 처음 반복할 때는 정렬 대상의 범위(데이터 크기)가 6개 이므로 5번 비교를 해서 하나를 제외하고 나면 정렬 대상의 범위(데이터 크기)가 5개가 되고 그때 4번을 비교하는 식으로 네 개일 때는 세번,두 개일 때는 한 번만 비교한다.
총 비교 횟수는 15=5+4+3+2+1이 됨. 식으로 나타내면 아래와 같이 나타냄.
버블 정렬의 비교 횟수 =. (n-1)+(n-2)+(n-3)...+(n-(n-2))+(n-(n-1)) = (n-1)+(n-2)+(n-3)...+3+2+1
첫 항(n-1)과 끝에서 첫 항 1을 더하면 n이됨. 즉 앞에서 m번째+뒤에서 m번째 = n
m이 가질 수 있는 최대의 값은 전체 항 개수의 절반 즉 n/2이다. 식으로 나타내면 아래와 같음.
(n-1)+(n-2)+(n-3)+...+3+2+1 = (n-1) * n / 2 = n(n-1) / 2

버블정렬의 장점은 구현이 간단해 버그를 만들 가능성이적다는 점. 단점은 비교연산의 양이 너무 많다.

5.3 삽입 정렬

삽입정렬(Insertion Sort): 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 적당한 곳에 삽입해 나가는 알고리즘.(ex카드정렬)
EX) 삽입정렬과정_오름차순(왼<오)
1.정렬대상(앞의 두 장의 카드)선택 후 오른쪽 카드가 왼쪽보다 큰지 비교
2.오른쪽 카드가 왼쪽 카드보다 작으면 그 카드를 뽑고 나머지 해당 카드보다 값이 큰 카드는 오른쪽으로 한자리씩 이동
3.이동하여 생긴 자리에 뽑았던 카드 삽입
4.정렬 대상을 하나 더 늘려서 즉 앞에서 비교했던 카드 포함해 한장을 더 추가한 3장을 비교
. . . 1 - 4과정 반복
삽입정렬은 만약 정렬할 필요가 없는 즉 오릌차순으로 이미 정렬된 상태면 비교할 필요 없이 다음단계로 넘어갑니다.
버블 정렬은 반드시 n(n-1)/2회의 비교를 거치지만 삽입 정렬은 선택한 정렬대상이 이미 정렬 되어있는 경운는 넘어갈 수 있기 때문에 버블정렬 보다는 더 나은 성능을 보입니다.

5.4 퀵 정렬

퀵 정렬(Quick Sort): 임의의 기준 요소를 선택해 기준보다 작으면 왼편에 크면 오른편에 분할하기 반복.

문제1. 배열은 분할을 어떻게 수행해야 하는가?(삽입/삭제가 자유롭지 못하므로)
'수색 섬멸'작전 사용.
1.양쪽 끝에서부터 접선할 때까지 기준보다 왼쪽은 기준보다 큰 요소 오른쪽은 기준보다 작은 요소를 찾아 교환 반복.
2.접선하면 기준 요소를 왼쪽 끝 요소와 교환.
문제2. 반복되는 분할 과정을 어떻게 처리하나?
재귀호출(RecursiveCall)로 함수 내에서 함수 자신을 호출해 반복되는 분할 과정을 처리.

[퀵 정렬 성능 분석]
:재귀 호출 깊이(반복 횟수 대신), 데이터 집합을 나누기 위하 비교 횟수로 성능을 분석함.
-최선의 경우: 퀵 정렬이 한번 호출될 때마다 집합이 1/2로 쪼개지는 경우.
재귀 호출 깊이:집합의 크기가 n개일때, log2n(2를 밑으로 하는 n의 로그)
ex) x=log10 1000(10을 밑으로 하는 1000의 로그)는 10의 3 거듭제곱이 1000이니 x=3임
비교횟수: 재귀 호출의 깊이 X 각 재귀 호출 단게에서의 비교 횟수 = n log2n

-최악의 경우
: 매 재귀 호출마다 데이터 집합의 분할이 1:n-1로 이루어지는 경우.
재귀 호출의 깊이: n-1
비교횟수: 매 재귀 호출시 정렬 대상의 범위도 1씩 줄어듬으로 n(n-1)/2회 비교해야함. 버블정령이나 삽입정렬의 성능과 비슷함.

-평균의 경우
:평균적으로 1.39nlog2n회 비교 수행.