[자료구조] 15강 탐색, 정렬

* 탐색

 

리스트에서 원하는 키를 찾고자 하는 방법을 탐색이라 하고 탐색 방법의 효율은 리스트에서 레코드들의 배열 순서에 대한 가정에 따라 달라진다.

레코드들이 키 필드 값의 순서로 배열되어 있을 경우에는 리스트를 효율적으로 탐색할 수 있다.

레코드들이 키 필드 값에 관계없이 임의 순서로 배열되어 있을 경우에는 리스트의 한쪽 끝에서 탐색을 시작해서 원하는 키를 찾거나 리스트의 다른 쪽 끝에 닿을 때까지 각 레코드를 조사해야한다.

주어진 리스트에서 원하는 키를 찾는 탐색으로 순차 탐색, 이진 탐색, 피보나치 탐색등이 있다.

 

1.순차 탐색

주어진 리스트에서 탐색키와 같은 레코드를 검색하는 방법으로 리스트에서 순차적으로 킷값을 탐색키와 비교하여 원하는 레코드를 찾는 방법

레코드들을 순차적으로 조사해서 순차 탐색(sequential search)라고 한다.

순차 탐색은 순서화되지 않은 레코드를 탐색하는 방법으로 탐색하고자 하는 레코드를 처음부터 마지막 레코드까지 저장되어 있는 순서대로 비교하면서 찾아내는 탐색 방법

배열이나 연결 리스트로 구현된 순차 자료구조에서 원하는 항목을 찾을 때 사용되는 기법

순차 탐색의 수행 시간은 레코드의 키를 비교하는 횟수에 좌우

비교 대상이 되는 레코드가 많은 경우에는 비효율적이지만 알고리즘이 단순하여 구현이 용이

 

2.이진 탐색

이진 탐색(Binary search)은 주어지는 리스트가 이미 순서화된 리스트로 전체 파일을 두 개로 분류해가면서 레코드를 찾아가는 방법

찾고자 하는 키와 중간 값을 비교하여 동일하면 탐색을 종료하고 비교 결과에 따라 한쪽 부분만을 탐색해가면서 원하는 키를 찾을 때 까지 반복하는 방법

 

3.피보나치 탐색

피보나치 수열을 잉ㅇ한 탐색 방법으로 피보나치 수열을 이용하여 서브 파일을 생성하면서 탐색하는 방법

이진 탐색보다 더 빠른 탐색이 가능하나 부가적인 연산에 의해 전체적인 효율이 떨어진다.

피보나치 탐색은 이진 탐색에서 다음 비교할 대상을 찾을 때 나눗셈으로 연산하지만 피보나치 탐색은 덧셈과 뺄셈만을 사용하므로 탐색 속도가 빠르다.

 

* 정렬

 

정렬이란 자료를 정렬하는 데 사용하는 기준이 되는 특정 값인 키를 이용하여 자료를 오름차순이나 내림차순으로 재배열하는 것을 의미한다.

정렬을 실행하는 방법에 따라서 비교하고자 하는 각 킷값들을 한 번에 두 개씩 비교하여 교환하는 방식으로 실행하는 방법을 비교식 정렬(comparative sort)이라 하고 킷값을 기준으로 하여 자료를 여러 개의 부분 집합으로 분해하여 각 부분 집합을 정렬함으로ㅆ 전체를 정렬하는 방식을 분산 식 정렬(distribute sort)라고 한다.

정렬하는 장소에 따라서 정렬할 자료를 메인 메모리에 올려서 정렬하는 내부 정렬(internal sort)과 정렬할 자료를 보조 기억장치에서 정렬하는 외부 정렬(external sort)이 있다.

내부 정렬은 속도는 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한적이라는 단점을 가진다.

외부 정렬은 대용량의 보조 기억장치를 사용하기 때문에 내부 정렬보다 속도는 떨어지지만 대용량의 자료에 대한 정렬도 가능하다는 장점을 가진다.

내부 정렬의 종류로는 버블 정렬(bubble sort), 선택 정렬(selection sort), 삽입 정렬(insertion sort), 기수 정렬(radix sort), 병합 정렬(merge sort), 쉘 정렬(shell sort), 히프 정렬, 퀵 정렬(quick sort)등이 있다.

외부 정렬은 병합 정렬이 주된 방법

정렬은 레코드의 수와 크기에 따라 적절한 정렬 방식을 선택해야한다.

정렬 알고리즘은 정렬을 진행하는데 있어서 취급되는 데이터의 양, 필요한 기억장소, 수행되는 시간등을 고려하여 효율적인지를 평가하게 된다.

 

1.삽입 정렬

가장 간단한 방식으로 정렬되어 있는 리스트에 킷값의 크기를 비교하여 순서위치를 찾아 삽입하는 n개의 키가 있다면 n-1단계의 수행 과정이 필요하다.

정렬되어 있는 킷값들을 삽입하고자 하는 값과 비교하여 큰 키들은 뒤로 이동한 후 삽입하는 방법이다.

삽입 정렬은 원소들이 이미 정렬되어 있어서 비교 횟수가 최소인 경우에 가장 최선의 경우로 전체 비교 횟수는 n-1번이고 시간 복잡도는 O(n)이 된다.

모든 원소가 역순으로 되어 있는 경우는 비교 횟수가 n(n-1)/2로 최대가 되며 시간 복잡도도 O(n제곱)이 된다.

최선의 경우 삽입 정렬의 평균 비교 횟수는 n(n-1)/4이면 평균시간 복잡도는 O(n제곱)이다.

 

2.쉘 정렬

삽입 정렬에서 한 자리씩 이동하면서 비교하는 과정을 개선하여 어떤 매개변수의 값으로 여러 개의 서브 파일을 구성하면서 각 서브 파일을 삽입 정렬 방식으로 배열하는 과정을 반복하는 방식

전체 원소에 대해서 삽입 정렬의 방식처럼 비교하는 작업보다는 부분으로 나누어 정렬하게 되므로 비교 연산과 교환 연산의 수가 현저히 감소

부분 집합의 기준값을 매 단계 감소시켜 가면서 정렬 단계를 반복

쉘 정렬의 interval은 전체 레코드 개수의 절반인 interval=n/2에서 시작해서 매번 interval=interval/2로 interval의 값이 0보다 큰 경우에 반복 수행

 

3.퀵 정렬

정렬 방법 중에 가장 빠른 정렬 방식으로 기준값을 중심으로 작은 원소들을 왼쪽 부분 집합으로 이동시키고 기준값을 중심으로 큰 원소들은 오른쪽 부분 집합으로 분할하여 정렬하는 방법

기준값을 중심으로 생성된 오니쪽 부분 집합과 오른쪽 부분 집합에 대해서 퀵 정렬을 순환적으로 반복

퀵 정렬은 정렬할 자료들을 기준값을 중심으로 2개의 부분 집합으로 분할(divide)하는 작업과 부분 집합의 원소들 중에서 기준값보다 작은 원소들을 왼쪽 부분 집합으로 기준값보다 큰 원소들은 오른쪽 부분 집합으로 정렬하는 정복(conquer)이라는 작업을 반복수행

이 과정은 부분 집합의 크기가 1이하기 될 때까지 반복

퀵 정렬은 총 비교 횟수는 n*log(n)으로 다른 정렬 방법에 비해 더 나은 시간 복잡도를 나타내어 성능이 좋은 알고리즘이다.

퀵 정렬의 최선의 경우는 피벗에 의해서 원소들이 왼쪽 부분 집합과 오른쪽 부분 집합으로 정확히 나누어 져서 수행 단계가 최소가 되는 경우가 해당

최악의 경우는 피벗에 의해 원소들을 분할하는 경우나 하나의 부분 집합으로 치우쳐지는 경우에 수행 단계가 최대가 되는 경우로 가장 최악의 경우에 해당

시간 복잡도는 O(nlon2n)로 다른 정렬 방법에 비해서 자리 교환 횟수가 줄어듬으로 실행시간의 성능이 좋은 방법이다.

퀵 정렬의 알고리즘은 각 부분 집합의 원소가 1이하가 될 때까지 반복하여 모든 원소들이 정렬이 되게 한다.

 

4.버블 정렬

버블 정렬은 주어진 리스트에서 인접한 2개의 레코드를 비교하여 서로 교환하는 방식으로 정렬

한 번의 단계를 거치면 리스트의 마지막에 가장 큰 레코드가 남게 된다.

인접한 2개의 레코드 간의 비교와 자리를 교환하는 과정을 반복

최선의 경우 비교 횟수 n(n-1)/2번, 교환 횟수는 발생하지 않는다

최악의 경우는 자료가 역순으로 되어 있는 경우로 비교 횟수는 최선의 경우와 동일하고 교환 횟수가 n(n-1)/2회가 된다

버블 정렬의 평균 시간 복잡도는 O(n제곱)이 된다.

 

5.2원 합병 정렬

이미 완전히 정렬이 된 서로 다른 2개의 파일을 합병하여 정렬된 1개의 리스트를 만드는 방식

정렬되지 않은 리스트를 2원 합병 정렬하기 위해서는 분할하는 과정을 먼저 진행하고 분할된 리스트를 2개씩 합병해 나가는 방식으로 재귀 호출을 통해 진행한다.

두 부분 집합 각각의 원소들을 비교하여 정렬된 하나의 리스트를 만들어 간다.

과정 반복을 통하여 분할된 각 부분 집합을 합병한 하나의 리스트가 될 때 까지 반복

n개의 원소를 분할하기 위핸 log2n의 단계를 수행하고 부분 집합의 원소를 비교하면서 합병하는 단계를 최대 n번비교 연산 수행하므로 2원 합병 정렬의 시간 복잡도는 O(lon2n)가 된다

 

6.히프 정렬

히프 정렬은 히프 트리를 이용하여 정렬하는 방식으로 항상 가장 큰 원소가 루트 노드가 되고 삭제 연산을 수행하면 항상 루트 노드의 원소를 삭제하여 반환하게 된다.

최대 히프의 경우는 내림차순 정렬을 수행하고 최소 히프의 경우는 오름차순 정렬이 수행된다.

히프 정렬 과정은 정렬할 원소들을 입력하여 최대 히프를 구성하고 루트 노드를 삭제하면서 정렬 리스트에 삽입

루트 노드가 삭제된 히프 노드를 다시 최대 히프로 구성하여 이전 과정을 트리의 노드가 없을 때 까지 반복 수행

최대 히프 트리는 원소의 값이 가장 큰 원소가 루프 노드가 되고 레벨 별로 원소의 크기 순이 된다.

히프 정렬은 각 단계별로 재구성하는 시간이 n개의 노드에 대해서 완전 이진 트리를 히프로 재구성해야 하므로 O(lon2n)이 되고 n개의 노드에 대해서 n번의 재구성이 이루어져야 하므로 평균 시간 복잡도는 O(nlog2n)이 된다.

 

7.선택 정렬

선택 정렬은 삽입 정렬의 빈번한 자료 이동을 개선한 방법으로 자료의 이동을 최소화하기 위한 정렬 방법

전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식

전체 원소들 중에서 가장 작은 원소를 찾아 선택하여 첫 번째 원소와 자리를 교환한다. 다음 두 번째로 작은 원소를 찾아 선택하여 두 번 째 원소와 자리를 교환한다. 이 과정을 반복하여 정렬하는 방식

선택 정렬 비교는 리스트의 개수만큼 비교하고 각 단계를 개수만큼 실행하므로 시간복잡도는 O(n제곱)dl 된다.

 

8.기수 정렬

대부분의 정렬 방법들은 레코드들을 비교함으로써 정렬을 수행하나 기수 정렬(radix sort)은 레코드를 비교하지 않고 정렬을 수행하는 방법

정렬할 수 있는 레코드의 타입이 한정된다는 점과 레코드의 키들이 동일한 길이를 가지는 숫자나 단순 문자이어야만 하는 단점을 가진다.

정렬할 원소의 킷값에 해당하는 버킷에 각 원소들을 분해하였다가 버킷의 순서대로 원소를 가져와서 나열하는 방법

킷값의 자릿수만큼 기수 정렬을 반복

기수 정렬의 연산 시간은 정렬할 원소의 수와 킷값의 자릿수에 따라 버킷의 수가 결정

원소를 각 버킷에 분배하는 작업 n+r 번과 키의 자릿수만큼 반복하는 작업이 d만큼 수행되므로 시간 복잡도는 O(d(n+r))이 된다.

이로써 자료구조 정리가 마무리 되었습니다. 더 이상의 자료구조 게시글은 없을 예정이며 추후 복습, 또는 추가 공부 내용에 따라 내용이 추가될수 있습니다.