[자료구조] 정렬 배열 (Sort Array)

정렬 배열: 

• 데이터가 정렬되어 잇는 것이 특징
• 선형 자료구조
• 이진 검색 알고리즘 적용 가능

✤ 자료구조의 연산에 관련 글은 이전 포스트를 참조해 주세요. (링크)

c#을 이용해 정렬 배열의 삽입, 선형검색, 이진 검색 구현해 보았다.

- 내부 배열 선언

1:  private const Int32 DefaultSize = 10;  
2:      private Int32[] arr;  
3:      private Int32 count;  

- 삽입

1:  /// <summary>  
2:      /// 데이터를 정렬하여 저장 합니다.  
3:      /// 최악의 경우 마지막 까지 검색해아 하며 (N),   
4:      /// 최악의 경우 배열 내 모든 값을 한 칸씩 오른쪽으로 이동 해야 하고 (N)  
5:      /// 1번의 삽입이 일어 난다   
6:      /// </summary>  
7:      /// <param name="value"></param>  
8:      public void Add(int value)  
9:      {  
10:        if (count == DefaultSize)  
11:          throw new ArgumentOutOfRangeException();  
12:    
13:        int firstRunner = 0;  
14:        // 추가 할 데이터 크기보다 큰 값의 인덱스를 찾는다.  
15:        while (firstRunner < count)  
16:        {  
17:          if (arr[firstRunner] > value)  
18:            break;  
19:    
20:          firstRunner++;  
21:        }  
22:    
23:        // 추가 데이터보다 큰 데이터는 오른쪽으로 이동 한다.  
24:        int lastRunner = count;  
25:        while (lastRunner >= firstRunner)  
26:        {  
27:          arr[lastRunner + 1] = arr[lastRunner];  
28:          lastRunner--;  
29:        }  
30:    
31:        arr[firstRunner] = value;  
32:    
33:        count++;  
34:      }  

- 선형 검색

1:  /// <summary>  
2:      /// 정렬된 배열의 선형 검색  
3:      /// 미리 정렬이 되어 있기에 찾고 자 하는 값이 없을 때 빨리 종료 할 수 있습니다.  
4:      /// 하지만 찾으려는 값이 마지막 값이거나, 마지막 값보다 크면 모든 셀을 검색해야 검색이 끝나는 단점이 있습니다.  
5:      /// (이는 선형 검색이 유일한 방법이라고 가정했을 경우 입니다)  
6:      /// </summary>  
7:      /// <param name="value"></param>  
8:      /// <returns></returns>  
9:      public int LinearSearch(int value)  
10:      {  
11:        foreach (var v in arr)  
12:        {  
13:          if (v == value)  
14:            return v;  
15:    
16:          if (value < v) break;  
17:        }  
18:    
19:        return -1;  
20:      }  

- 이진 검색

1:  /// <summary>  
2:      /// 이진 검색  
3:      /// </summary>  
4:      /// <param name="value"></param>  
5:      /// <returns></returns>  
6:      public int BinarySearch(int value)  
7:      {  
8:        // 값이 있을 수 있는 상한선과 하한선을 정한다.  
9:        // 최초의 상한선은 배열의 첫 번째 값, 하한선은 마지막 값  
10:        int lowerBound = 0;  
11:        int upperBound = count - 1;  
12:    
13:        // 상한선과 하한선 사이의 가운데 값을 계속해서 확인하는 루프 시작  
14:        while (lowerBound <= upperBound)  
15:        {  
16:          // 상한선과 하한선의 중간 지점을 찾는다.  
17:          int midPoint = (upperBound + lowerBound) / 2;  
18:    
19:          int midValue = arr[midPoint];  
20:    
21:          // 중간 값이 찾으려는 값보다 크면 상한선을  
22:          if (value < midValue)  
23:            upperBound = midPoint - 1;  
24:          else if (value > midValue)  
25:            lowerBound = midPoint + 1;  
26:          else if (value == midValue)  
27:            return midPoint;  
28:        }  
29:    
30:        return -1;  
31:      }