[Algorithm] 정렬 알고리즘

선택 정렬

1. 가장 작은 데이터를 선택

2. 맨 앞에 있는 데이터와 바꿈

3. 그 다음 작은 데이터를 선택

4. 앞에서 두 번째 데이터와 바꿈 -> 배열 끝날 때까지 반복

- 선택 정렬의 시간복잡도 : O(N^2)
    -> 매우 비효율적 

- 공간 복잡도: O(1)

int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };

for (int i = 0; i < arr.Length - 1; i++)
{
    int minIndex = i;
	// 같은 숫자 비교하지 않는다 (j = i+1)
    for (int j = i + 1; j < arr.Length; j++)
    {
        if (arr[j] < arr[minIndex])
        {
            minIndex = j;
        }
    }
	
    // for문을 돌며 가장 작은 수의 인덱스를 얻었으므로 swap
    int temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
}

삽입 정렬

- 특정한 데이터를 적절한 위치에 삽입
- 두 번째 데이터부터 정렬, 자기보다 작은 데이터를 만나면 바로 그 오른쪽에 삽입
- 기준 데이터의 왼쪽에 있는 데이터들은 이미 정렬이 된 상태!!

- 시간복잡도 : O(N^2)
    -> 데이터가 거의 정렬되어 있는 최선의 경우 퀵정렬 보다 빠르고 O(N) 의 시간복잡도 
- 공간 복잡도: O(1)

int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };

for (int i = 1; i < arr.Length; i++)
{
	// j는 arr[i] 앞의 숫자
    int j = i - 1;
    int key = arr[i];
    
    // 앞의 숫자가 양수이고 기준 숫자보다 크다면 swap
    while (j >= 0 && arr[j] > key)
    {
        arr[j + 1] = arr[j];
        j--;
    }

    arr[j + 1] = key;
}

퀵 정렬

[알고리즘] 퀵 정렬(quick sort)

예전에 정리해둔 내용

 

 

병합 정렬

1. 배열을 반으로 나눔

2. 각 부분을 재귀적으로 정렬 & 병합

 

- 시간 복잡도: O(nlogn)
- 공간 복잡도: O(n) 

void MergeSort(int[] arr, int left, int right)
{
    if (left < right)
    {
        int mid = (left + right) / 2;
        
        // 중간 기준으로 재귀 호출
        MergeSort(arr, left, mid);
        MergeSort(arr, mid + 1, right);
        
        Merge(arr, left, mid, right);
    }
}

void Merge(int[] arr, int left, int mid, int right)
{
    int[] temp = new int[arr.Length];

    int i = left;
    int j = mid + 1;
    int k = left;

    while (i <= mid && j <= right)
    {
        if (arr[i] <= arr[j])
        {
            temp[k++] = arr[i++];
        }
        else
        {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid)
    {
        temp[k++] = arr[i++];
    }

    while (j <= right)
    {
        temp[k++] = arr[j++];
    }

    for (int l = left; l <= right; l++)
    {
        arr[l] = temp[l];
    }
}

int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };

MergeSort(arr, 0, arr.Length - 1);