알고리즘

본문내용

알고리즘 : 어떤 문제에 대한 해결방법이다. 여러가지 방법중에 최적의 알고리즘을 선택한다면 프로그램상의 시간이나 메모리 공간의 효율성을 기대할 수 있다.
정렬 : 주어진 데이터를 어떤 기준(오름차순(Ascending), 내림차순(Descending))에 의해 순서대로 나열하는 것이다. 정렬에는 주기억 장치 안에서 정렬하는 내부정렬과 보조기억장치를 이용하는 외부정렬이 있다.
퀵(Quick)정렬 : 평균 실행시간이 O(n log n)이 걸리는 비교적 안정적인 정렬방법이다.
어떤 기준값을 중심으로 왼쪽에서 큰값을 검색하고, 오른쪽에서 작은값을 검색하여 두 수를 교환하며 계속 반복하면서, 왼쪽의 첨자가 오른쪽의 첨자보다 커질 때 기준값과 오른쪽의 값을 교환하는 방법이다. 기준값을 중심으로 왼쪽과 오른쪽을 분할하여 다시 분할되지 않을때까지 반복수행하는 알고리즘이다.
예) 다음의 데이터를 퀵정렬의 알고리즘으로 정렬하시오.
레벨 1 30 20 40
35 5 10 45 50 25 15
배열의 첫번째 값인 30을 기준으로 왼쪽부터는 큰값이 있는지 검색하고, 오른쪽 부터는 작은값이 있는지 검색하여 두 수를 교환한다.
레벨 1 30 20 15 35
5 10 45 50 25 40
레벨 1 30 20 15 25 5 10 45 50 35 40
왼쪽부터 찾기 시작한 값은 30보다 큰 45이고 오른쪽부터 찾기 시작한 값은 30보다 작은 10이다. 왼쪽 포인터가 오른쪽 포인터보다 커지면 기준값과 오른쪽 값을 교환하고 현재 레벨이 끝난다.
레벨 1 10 20 15 25 5 30 45 50 35 40
레벨 1의 수행한 후 완료된 모습
다음 레벨은 30을 중심으로 왼쪽과 오른쪽이 나뉘어서 왼쪽부터 검색하여 교환한다.

키워드

알고리즘,   알고리즘 강좌,   알고리즘 정리,   알고리즘 내용정리,   퀵(Quick)정렬,   정렬,   탐색법