[알고리즘]알고리즘

소개글

알고리즘 리포터였습니다.

목차

- Quicksort 알고리즘, 재현식 산출, 평균시간 복잡도를 적용한 시간복잡도 분석
- Quicksort를 동료또는 후배에게 설명하고 이해시키시오.
- 제출자료 : 설명 및 질의응답내용 (본인이 이해하지 못하는 부분에 이해과정포함)

본문내용

* 친구와 나의 대화 *
나 : 데이터를 정렬하는 방법 중에서 제일 빠르다는 Quicksort알고리즘에 대해 공부해보자.
우선 정렬이란 말은 들어본 적 있니?

질문 : 나도 데이터를 오름차순이나 내림차순으로 순차나 교환정렬하는 간단한 프로그래밍은 본적이 있어. Quicksort라는 말은 얼핏 들어본 방법이긴 한데 사실 잘 이해가 안 가더라구. 먼저 어떻게 데이터를 정렬하는지 설명해죠.

나 : 우선 Quicksort알고리즘의 원리는 분할정복식 접근방법 중에 하나로써, 말 그대로 데이터를 분할하고 분할된 작은 경우에서 데이터를 찾거나 문제의 해답을 얻고 나서 답들을 통합하여 전체의 답을 구하는 방법으로 이루어진 방법이야. 데이터가 많은 경우 부분을 잘라서 비교나 검색하면 크기가 작아지니깐 데이터비교가 훨씬 빠르게 이루어 질수 있는거지.

최대한 쉽게.. 예를 들어 설명해 볼게. 그림을 보면서 공부해보자.

Quicksort는 배열을 두 부분으로 분할 한 다음, 각 분할된 부분을 재귀적으로 정렬하여 정렬을 수행하는데, 어떤 기준 아이템(Pivot item)보다 작은 아이템들은 모두 그 앞부분으로 위치시키고 그 기준 아이템보다 크거나 같은 아이템들은 모두 그 뒷부분에 위치시키는 거야. 그림상 예제에 숫자가 마구 섞여있지? "26 5 37 1 61 11 59 15 48 19" 섞인 수중에 그냥 임의로 맨 앞에 있던 수 “26”을 기준(Pivot)으로 잡은 거야.

“26”을 기준으로 데이터 하나하나를 앞에서 말했던 방법으로.. “26”보다 작은 것은 앞부분(왼쪽), 큰 것은 뒷부분(오른쪽)에 배치하는 거지.

“26”을 기준으로 기본배치가 다 끝났다고 하면..
문제는 앞부분과 뒷부분은 정렬이 되지 않고 그냥 배치만 된 상태이자나.
각 부분의 정렬문제가 남은 거야.
즉 “26”을 기준으로 전체데이터가 분할되었다는 것을 알 수 있어.

그럴 경우 각 분할된 부분별로 서로 다른 기준(Pivot)을 만들어 재배치를 하는 거지.
앞부분 기준(Pivot)을 “11”로 새로이 만들어 앞의 방법과 같이 “11”보다 작은 것은 앞부분, 큰 것은 뒷부분에 위치 시켜 보자.

그런데 이런 정렬 방법은 조금 수동적이라 느끼지 않아? 우리가 맨 앞의 숫자를 기준점으로 잡아 배치시키니 말야. 이런 작업은 Quicksort의 수동적인 수행절차를 느낄 수 있어.

참고 자료

없음