탐색과 정렬

<탐색>

1. 컴퓨터에 장한 자료 중에서 원하는 정보를 찾는 작업

2. 삽입이나 삭제 작업에서는 원소를 삽입하거나 삭제할 위치를 찾기 위해서 탐색을 수행

3. 효율적인 탐색을 위해 데어터를 빠르게 탐색할 수 있도록 잘 정리하고 분류하는 것도 중요

 

<탐색기>

1. 다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드

2. 항목과 항목을 구별시켜주는 키

3. 탐색이란 탐색키와 데이터로 이루어진 여러 개의 항목 중에서 원하는 탐색키를 가지고 있는 항목을 찾는 것

 

<순차 탐색>

1. 일렬로 나열된 데이터를 처음부터 마지막까지 순서대로 탐색하는 방법

2. 순서화되어 있지 않은 경우 사용

3. 탐색해야 하는 데이터의 양에 따라 효율이 달라지는데 데이터의 양이 많으면 탐색 시간이 증가

4. 선형 탐색이라고도 함

5. 데이터 비교 횟수는 찾고자 하는 데이터의 저장 위치에 따라 다름(맨 앞에 있으면 비교를 1번 만에 성공하고 n번째 있으면 n번만큼의 비교가 필요)

6. 순차 탐색의 평균 비교 횟수는 (1+2+3+..+n)/n = (n+1)/2이므로 순차 탐색의 시간 복잡도는 O(n)

 

<순차 탐색 알고리즘>

int seq_search(int list[], int key, int low, int high)

{

   for(int i=low; i<=high; i++)

       if(list[i] = key) then

          return i; /* 탐색에 성공하면 킷값의 인덱스 반환 */

   return -1;  /* 탐색에 실패하면 -1을 반환 */

}

<순차 탐색을 개선한 방법>

1. 전진 이동법

   한 번 탐색된 데이터는 다음에 다시 탐색될 가능성이 높다는 가정에 따라 어떤 데이터가 한 번 탐색되고 나면 그 데이터를 데이터 집합의 가장 앞에 위치시키는 방법

2. 전위법

   전진 이동법과는 달리 자주 사용되면 사용될수록 점진점으로 해당 항목을 데이터 집합의 앞쪽으로 이동시킴

   특정 데이터만 탐색되지 않고 모든 데이터가 균등하게 탐색될 확률을 갖는 경우에 적합

3. 빈도 계수법

   데이터 집합 내의 각 항목들이 탐색된 횟수를 별도의 공간에 저장해 두고 탐색된 횟수가 높은 순으로 데이터 집합을 재공하는 방법

 

<이진 탐색>

1. 정렬된 데이터 집합을 이분화하면서 탐색하는 방법

2. 자료의 가운데에 있는 항목을 킷값과 비교하여 다음 검색 위치를 결정하여 검색을 계속하는 방법

3. 가운데 있는 값을 기준으로 왼쪽과 오른쪽 두 부분으로 나누어서 탐색하고 한번 탐색할 때마다 탐색 대상이 절반으로 줄어듦

4. 데이터의 수가 많을수록 더 효율적

5. 데이터들이 정렬되어 있는 경우 순차 탐색보다는 탐색 속도가 훨씬 빠름

6. 시간 복잡도는 O(log₂n)

 

<이진 탐색을 수행하는 과정>

1. 데이터 집합의 중간에 있는 값을 선택한다.

2. 중간값과 찾고자 하는 목표값을 비교한다.

3. 목표값이 중간값보다 작으면 중간값의 왼편에 대해 이진 탐색을 수행하고, 목표값이 중간값보다 크면 오른편에 대해 이진 탐색을 수행한다.

4. 찾고자 하는 값을 찾을 때까지 1~3을 반복한다.

 

<삽입 정렬을 수행하는 과정>

1. 처음 A[0]은 정렬된 데이터로 취급한다.

2. 다음 데이터 A[1]은 정렬된 데이터 A[0]과 비교하여 적절한 위치에 삽입한다.

3. 다음 데이터 A[2]는 정렬된 데이터 A[0], A[1]과 비교하여 적절한 위치에 삽입한다.

4. 같은 방식으로 나머지 데이터들을 삽입하여 정렬한다.

 

<삽입 정렬 알고리즘>

insertion_sort(A[], n)

{

  for i = 1 to n-1 {

      CurrentElement = A[i]; /* i는 현재 원소 */

       j = i-1; /* 현재 원소를 정렬된 앞부분에 삽입하기 위해 */ 

      while(j>=0 && A[j]>CurrentElement){

              A[j+1] = A[j]; /*자리 이동 */

              j = j-1;

     }

       A[j+1] = CurrentElement;

  }

}

 

<쉘 정렬>

1. 삽입 정렬의 개념을 확대하고 일반화한 것

2. 일정한 간격으로 떨어져있는 데이터들끼리 부분 리스트를 구성하고 각 부분 리스트에 있는 데이터들에 대해서 삽입 정렬을 수행하는 작업을 반복하면서 전체 데이터들을 정렬하는 방법

3. 멀리 떨어진 데이터들이 하나의 서브 리스트로 구성되도록 하여 멀리 떨어진 데이터들 사이에 비교 및 교환이 수행되는 정렬 방법

4. 쉘 정렬 단계를 거치면서 데이터들이 점진적으로 정렬된 상태가 되기 때문에 마지막 삽입 정렬의 속도가 빨라짐

5. 쉘 정렬 간격은 계속 줄여나가되 마지막에는 간격을 반드시 1로 설정해야 함(아직 크기 비교가 되지 않은 다른 그룹의 숫자가 있을 수 있기 때문)

6. 쉘 정렬의 시작 복잡도는 간격에 따라 다름(가장 좋은 간격을 알면 빨라짐)

7. 최악의 경우 시간 복잡도는 O(n²)이며 평균적인 경우 시간 복잡도는 O(n^1.5)

shell_sort(A[], n)

{

  for each gap h = [h0 > h1 > ... > hk=1] /* 큰 gap부터 차례로 지정 */

  for i = h to n-1{

       CurrentElement = A[i];

       j = i;

       while(j >= h && A[j-h] > CurrentElement){

             A[j] = A[j-h];

             j = j-h;

       }

         A[j] = CurrentElement;

    }

}

 

<퀵 정렬>

1. 다른 알고리즘에 비해 평균적으로 수행 속도가 매우 빠른 정렬 방법

2. 정렬할 전체 데이터에 대해서 정렬을 수행하지 않고 피벗을 중심으로 왼쪽 부분 리스트와 오른쪽 부분 리스트로 분할하여 정렬하는 방법

3. 피벗을 기준으로 왼쪽 부분 리스트에는 피벗보다 작은 데이터들을 이동시키고 오른쪽 부분 리스트에는 피벗보다 큰 데이터들을 이동시킴

4. 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법

5. 분할 정복 알고리즘의 일종

6. 정렬 방법 중에서 가장 빠른 방법이며 순환 호출을 이용하므로 스택이 필요

7. 평균적인 시간 복잡도는 O(nlog₂n)

 

<퀵 정렬을 수행하는 과정>

1. 리스트의 첫 원소를 피벗으로 선택한다.

2. 피벗의 다음 위치로부터 오른쪽으로 움직이면서 크기를 비교하여 피벗보다 큰 데이터를 찾는다.

3. 동시에 리스트의 마지막부터 왼쪽으로 움직이면서 피벗보다 작은 데이터를 찾아 서로 교환한다.

4. 피벗을 중심으로 나누어진 각 서브 리스트에서 1부터 다시 반복한다.

 

<버블 정렬>

1. 이웃하는 데이터를 비교하여 작은 데이터를 앞쪽으로 이동시키는 과정을 반복하여 정렬하는 알고리즘
2. 주어진 파일에서 인접한 2개의 데이터를 비교하여 그 크기에 따라 데이터의 위치를 서로 교환하는 정렬 방식
3. 매우 단순하지만 정렬할 데이터가 많은 경우에는 수행 시간이 많이 걸림
4. 평균적인 시간 복잡도는 O(n²)

<버블 정렬을 수행하는 과정>

 

1. 인접한 두 데이터 A[i] 와 A[i+1]의 값들을 비교한다.
2. A[i+1]의 값이 A[i]의 값보다 작으면 두 데이터를 교환한다.
3. 이 과정을 반복하면 큰 데이터가 배열의 끝에 오도록 정렬된다.

<2원 합병 정렬>

1. 하나의 리스트를 두 개의 균등한 크기로 반복해서 분할한 뒤 분할된 부분 리스트를 정렬한 다음 두 리스트를 합하여 전체가 정렬된 리스트를 만드는 방법
2. 분할 과정을 거쳐 두 개로 분할된 부분 리스트를 각각 정렬하고 완전히 정렬된 서로 다른 두 개의 부분 리스트를 합병하여 완전히 정렬된 한 개의 리스트로 만드는 것
3. 합병 정렬의 시간 복잡도는 O(nlog₂n)

<2원 합병 정렬의 세가지 동작>
1. 분할(divide): 입력 데이터를 같은 크기의 부분 리스트 2개로 분할한다.
2. 정복(conquer): 부분 리스트의 데이터들을 정렬한다.
3. 결합(combine): 정렬된 부분 리스트들을 하나의 리스트로 통합한다.

<히프 정렬>
1. 히프라는 특수한 자료구조를 사용하는 정렬 알고리즘
2. 최대 히프는 부모 노드의 킷값이 자식 노드의 킷값보다 항상 크거나 같은 크기 관계의 히프
3. 최소 히프는 부모 노드의 킷값이 자식 노드의 킷값보다 항상 크거나 같은 크기 관계의 히프
4. 정렬하고자 하는 데이터들이 있을 때 모든 데이터들을 히프에 삽입하여 히프를 완성한 후 하나씩 삭제하면 정렬된 순서대로 데이터들이 빠져나오게 되는데 이것이 히프 정렬이 됨
5. 히프 정렬의 시간 복잡도는 O(nlog₂n)

<히프 정렬에 필요한 과정>
1. 주어진 데이터들로 구성하는 트리를 히프로 만드는 과정
2. 히프에서 루트 노드를 제거하고 나서 나머지를 히프로 재구성하는 과정을 반복

<히프 정렬이 수행되는 과정>
1. 히프에서 루트 노드의 킷값을 출력한다.
2. 히프의 마지막 노드를 루트 노드로 가정하여 나머지 노드들로 새로운 히프를 만든다.
3. 해로 만들어진 히프 트리의 루트 노드를 출력하고 앞에서 만든 히프의 마지막 노드를 루트 노드로 가정하여 새로운 히프를 만드는 과정을 반복한다.
4. 3의 과정을 모든 노드가 제거될 때까지 반복한다.

<선택 정렬>
1. 전체 데이터들 중에서 기준 위치에 맞는 데이터를 선택하여 자리를 교환하는 방식으로 정렬
2. 정렬되지 않은 데이터들에 대해 오름차순으로 정렬하고자 한다면 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해 나가는 방법을 반복하는 방법
3. 데이터의 이동을 최소화하여 정렬하는 방법
4. 시간 복잡도는 O(n²)

<선택 정렬을 수행하는 과정>
1. 전체 데이터 중에서 가장 작은 데이터를 찾아서 선택하여 첫 번째 위치와 자리를 교환한다.
2. 그다음 두 번째로 작은 데이터를 찾아 선택하여 두 번째 위치와 자리를 교환한다.
3. 그다음에는 세 번째로 작은 데이터를 찾아서 세 번째 위치와 자리를 교환한다.
4. 이 과정을 반복하면서 정렬을 완성한다.

<기수 정렬>
1. 제한적인 범위 내에 있는 숫에 대해서 각 자릿수별로 정렬하는 알고리즘
2. 비교 정렬이 아니며 숫자를 각 자릿수에 대해 부분적으로 비교하는 정렬 방법
3. 원소의 킷값을 나타내는 기수를 이용한 정렬 방법
4. 시간 복잡도는 O(d(n+r))

<기수 정렬을 수행하는 과정>
1. 먼저 정렬하고자 하는 숫자들을 먼저 가장 낮은 자릿수만 가지고 모든 수를 재배열(정렬)한다.
2. 그런 다음 가장 낮은 자릿수는 제외하고 나머지 자릿수에 대해 다시 앞과 같이 반복한다.
3. 더 이상 자릿수가 남지 않을 때까지 계속하면 마지막에는 정렬된 배열을 갖게 된다.