정렬 알고리즘

파이썬에서는 sort(), C#에서는 System.Linq의 OrderBy() 메소드가 있다.
쉽게 그냥 사용해도 되지만 구현 방법 정도는 알고 넘어가야제.

선택 정렬

배열 내의 최솟값을 찾아 맨 앞에 배치하는 방법이다.
시간 복잡도 : 평균적으로 O(N^2)

파이썬 코드

def SelectSort(arr):
    for i in range(len(arr)):
        minIndex = i

        for j in range(i + 1, len(arr)):
            if arr[minIndex] > arr[j]:
                minIndex = j
        
        arr[i], arr[minIndex] = arr[minIndex], arr[i]

    return arr

C# 코드

int[] SelectSort(int[] arr)
{
    for (int i = 0; i < arr.Length; i++)
    {
        int minIndex = i;

        for (int j = i + 1; j < arr.Length; j++)
        {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }

        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }

    return arr;
}

삽입 정렬

정렬되지 않은 부분에서 요소를 가져와 정렬된 부분에 적절한 위치에 삽입하는 방법이다.
시간 복잡도 : 최선의 경우 O(N), 최악의 경우 O(N^2)

파이썬 코드

def InsertSort(arr):
    for i in range(1, len(arr)):
        for j in reversed(range(1, i+1)):
            if arr[j] < arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
            else:
                break

    return arr

C# 코드

int[] InsertSort(int[] arr)
{
    for (int i = 1; i < arr.Length; i++)
    {
        int temp = arr[i];
        int j;

        for (j = i - 1; j >= 0; j--)
        {
            if (arr[j] < temp)
                break;

            arr[j + 1] = arr[j];
        }

        arr[j + 1] = temp;
    }

    return arr;
}

퀵 정렬

pivot을 기준으로 작은 요소들은 왼쪽, 큰 요소들은 오른쪽으로 분할하고 이를 재귀적으로 정렬하는 방법이다.
시간 복잡도 : 평균적으로 O(logN), 최악의 경우 O(N)

파이썬 코드

def QuickSort(arr):
    if not arr:
        return []

    pivot = arr[0]
    remain = arr[1:]

    left = [x for x in remain if x <= pivot]
    right = [x for x in remain if x > pivot]

    return QuickSort(left) + [pivot] + QuickSort(right)

C# 코드

void QuickSort(int[] arr, int left, int right)
{
    if (left < right)
    {
        int pivot = Partition(arr, left, right);

        QuickSort(arr, left, pivot - 1);
        QuickSort(arr, pivot + 1, right);
    }
}

int Partition(int[] arr, int left, int right)
{
    int pivot = arr[right];
    int i = left - 1;

    for (int j = left; j < right; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            Swap(arr, i, j);
        }
    }

    Swap(arr, i + 1, right);

    return i + 1;
}

void Swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

파이썬은 배열 원소끼리 swap 하기도 편하고 간결한 느낌이 좋다... 하지만 이젠 C#에도 익숙해지자... 그렇지만 코딩 테스트 때문에 파이썬도 소홀히 하면 안된다... 그래도 Unity 쓰려면 C#도 소홀하면 안된다... 진짜 내 마음은 뭘까.....

---

세줄 요약

• 소팅 공부함
• 역시 PYTHONIC
• 그치만 C# 문법도 익숙해져야 한다.