알고리즘 정리

소개글

"알고리즘 정리"에 대한 내용입니다.

목차

없음

본문내용

알고리즘 : 어떤 문제에 대한 해결방법이다. 여러가지 방법중에 최적의 알고리즘을 선택한다면 프로그램상의 시간이나 메모리 공간의 효율성을 기대할 수 있다.

정렬 : 주어진 데이터를 어떤 기준(오름차순(Ascending), 내림차순(Descending))에 의해 순서대로 나열하는 것이다. 정렬에는 주기억 장치 안에서 정렬하는 내부정렬과 보조기억장치를 이용하는 외부정렬이 있다.

퀵(Quick)정렬 : 평균 실행시간이 O(n log n)이 걸리는 비교적 안정적인 정렬방법이다.
어떤 기준값을 중심으로 왼쪽에서 큰값을 검색하고, 오른쪽에서 작은값을 검색하여 두 수를 교환하며 계속 반복하면서, 왼쪽의 첨자가 오른쪽의 첨자보다 커질 때 기준값과 오른쪽의 값을 교환하는 방법이다. 기준값을 중심으로 왼쪽과 오른쪽을 분할하여 다시 분할되지 않을때까지 반복수행하는 알고리즘이다.
왼쪽부터 검색한 10보다 큰값은 15이고, 오른쪽부터 검색한 10보다 작은값은 5이다. 왼쪽부터 검색한 포인터가 오른쪽부터 검색하기 시작한 포인터보다 크므로 기준값인 10과 오른쪽부터 검색하기 시작한 5와 교환한다. 그리고 레벨 2가 끝난다.
다음 레벨은 10을 중심으로 왼쪽과 오른쪽을 분할하여 왼쪽부터 검색하지만, 값이 하나이므로 그 값은 그대로 사용하고 오른쪽부터 정렬한다.
15를 기준으로 15보다 큰수는 25가 있지만 15보다 작은수가 없으므로 교환은 이루어지지 않고 레벨이 끝난다.

참고 자료

없음