C# #9 알고리즘 기초 2

선택정렬(Selection Sort)

• 선택정렬은 가장 작은/큰 데이터를 맨 앞으로 순서대로 이동시켜 정렬시키는 알고리즘이다.
• 첫 번째 루프에서, 첫 번째 인덱스의 값(data[0])과 나머지 인덱스의 값들과 비교하여 가장 작은 값을 첫 번째 인덱스의 값과 교환한다.
• 두 번째 루프에서, 두 번째 인덱스의 값(data[0+1])과 나머지 인덱스의 값들과 비교하여 가장 작은 값을 두 번째 값과 교환한다.(첫 번째 값은 제외)
• 이런 방식으로 배열 길이 만큼 루프 반복을 하여 순서대로 데이터를 정렬시킨다.
• SWAP 코드: 두 변수를 바꾸려면 기존의 값을 저장하는 변수(temp)가 하나 더 필요하다.

//Input
int[] data = { 3, 2, 1, 4, 5 };
int N = data.Length; //의사코드

//Process: Selection SORT
for (int i = 0; i < N - 1; i++) //i = 0 to N-1
{
    for (int j = i + 1; j < N; j++) //j = i+1 to N
    {
        if (data[i] > data[j]) //부등호 방향에 따라 오름차순(>), 내림차순(<)
        {
        //SWAP 코드
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
        }
    }
}
            
//Output
for (int i = 0; i < N; i++)
{
    Console.WriteLine($"{data[i]}");
}

 

이진탐색(Binary Search)

• 이진탐색은 정렬되어 있는 데이터를 반씩 나눠서 검색하는 알고리즘이다.
• 정렬되어 있는 데이터의 최솟값 인덱스(첫 번째 인덱스), 최댓값 인덱스(마지막 인덱스)을 변수로 지정한다.
• 데이터의 중간값 인덱스를 변수로 지정한다. ( 중간값 인덱스 = (최솟값 인덱스 + 최댓값 인덱스)/2 )
• 첫 번째 루프에서, 타겟 값과 중간값 인덱스의 값과 비교하였을 때, 중간값 인덱스의 값이 더 크면 자료구조의 왼쪽 영역만 탐색하고 더 작으면 오른쪽 영역을 탐색한다.
• 두 번째 루프에서, 왼쪽 영역 탐색의 경우 [최댓값 인덱스 - 1]로 다시 세팅하여 중간값 인덱스를 다시 계산하고 첫 번째 루프의 작업을 반복한다. 오른쪽 영역 탐색의 경우 [최솟값 인덱스 + 1]로 세팅하여 동일하게 작업을 진행한다. 
• 이런 방식으로 루프 반복한 후, 중간값 인덱스의 값과 검색 타겟 값이 같을 때, 회전을 종료한다.

//Input
int[] data = { 1, 3, 5, 7, 9 }; //오름차순으로 정렬되어 있음.
int N = data.Length; //의사코드
int search = 3; //검색할 데이터
bool flag = false; //찾으면 true, 찾지 못하면 false
int index = -1; //찾은 위치, 찾지 못하면 -1

//Process:Binary SEARCH
int low = 0; //min: 낮은 인덱스
int high = N - 1; //max: 높은 인덱스
while(low <= high)
{
    int mid = (low + high) / 2; //중간 인덱스(정수)
    if (data[mid] == search)
    {
        flag = true;
        index = mid;
        break;
        //찾으면 플래그, 인덱스 저장 후 반복 종료
    }
    if (data[mid] > search)
    {
        high = mid - 1; //찾을 데이터가 작으면 왼쪽 영역으로 이동
    }
    else
    {
        low = mid + 1; //찾을 데이터가 크면 오른쪽 영역으로 이동
    }
}

//Output
if(flag==true)
{
    Console.WriteLine($"{search}을 {index}위치에서 찾았습니다.");
}
else
{
    Console.WriteLine("찾지 못했습니다.");
}

 

오늘은 선택과 정렬 알고리즘 중 가장 기초적인 한가지 방법들을 살펴보았다. 추후에 다양한 선택, 정렬 알고리즘들을 더 알아보고 각자의 동작 원리와 장단점을 비교 분석해볼 예정이다.