11.17 (TIL)

정렬 알고리즘

1) 정렬 알고리즘 이란?

정렬 알고리즘은 컴퓨터 과학에서 중요한 주제 중 하나

주어진 데이터 세트를 특정 순서(대개는 숫자의 오름차순 또는 내림차순, 문자열의 사전식 순서)로 배열하는 방법을 제공

 

2) 선택 정렬 ( Selection Sort )

선택 정렬은 배열에서 최소값(또는 최대값)을 찾아 맨 앞(또는 맨 뒤)와 교환하는 방법

시간 복잡도: 최악의 경우와 평균적인 경우 모두 O(n^2)

공간 복잡도: O(1) (상수 크기의 추가 공간이 필요하지 않음)

 

간단 예제1

def selection_sort(arr):
    """
    선택 정렬 알고리즘을 사용하여 배열을 정렬하는 함수
    :param arr: 정렬되어야 할 배열
    :return: 정렬된 배열
    """
    n = len(arr)

    # 배열의 각 요소를 순회
    for i in range(n - 1):
        # 현재 인덱스를 최소값으로 가정
        min_index = i

        # 현재 인덱스 이후의 모든 요소를 순회하며 최소값을 찾음
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        # 최소값을 현재 인덱스와 교환
        arr[i], arr[min_index] = arr[min_index], arr[i]

    return arr

# 예시 배열
my_array = [64, 25, 12, 22, 11]

# 선택 정렬 실행
sorted_array = selection_sort(my_array)

# 정렬 결과 출력
print("정렬된 배열:", sorted_array)

 

// 선택 정렬은 두 개의 중첩된 반복문을 사용

// 외부 반복문은 배열의 각 요소를 선택하고,

// 내부 반복문은 현재 요소 이후의 모든 요소를 순회하여 최소값을 찾는다.

// 최소값을 현재 인덱스와 교환하는 과정을 반복

// 이렇게 반복하면서 전체 배열이 정렬

 

간단 예제2

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

// 외부 반복문: 배열의 각 요소를 선택
for (int i = 0; i < arr.Length - 1; i++)
{
    // 현재 인덱스를 최소값으로 가정
    int minIndex = i;

    // 내부 반복문: 현재 인덱스 이후의 모든 요소를 순회하여 최소값 찾기
    for (int j = i + 1; j < arr.Length; j++)
    {
        if (arr[j] < arr[minIndex])
        {
            // 최소값의 인덱스 업데이트
            minIndex = j;
        }
    }

    // 현재 인덱스의 값과 최소값의 값을 교환
    int temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
}

// 정렬된 배열 출력
foreach (int num in arr)
{
    Console.WriteLine(num);
}

 

// 초기 배열: {5, 2, 4, 6, 1, 3}

 

// 선택 정렬 알고리즘 설명:

외부 반복문은 배열의 각 요소를 선택하는 역할

내부 반복문은 현재 선택된 요소 이후의 모든 요소를 순회하여 최소값을 찾는다

최소값을 찾으면 그 인덱스를 minIndex에 저장

 

// 교환 과정 설명:

외부 반복문의 각 단계에서 내부 반복문을 통해 최소값의 인덱스(minIndex)가 결정.

현재 선택된 요소와 최소값을 가진 요소의 값을 교환

 

// 정렬 후 배열: {1, 2, 3, 4, 5, 6}

 

// 결과 출력:

foreach 루프를 사용하여 정렬된 배열을 출력

 

 

3) 삽입 정렬 ( Insertion Sort )

삽입 정렬은 정렬되지 않은 부분에서 요소를 가져와 정렬된 부분에 적절한 위치에 삽입하는 방법

시간 복잡도: 최악의 경우 O(n^2), 하지만 정렬되어 있는 경우에는 O(n)

공간 복잡도: O(1) (상수 크기의 추가 공간이 필요하지 않음)

 

간단 예시1

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

// 외부 반복문: 배열의 각 요소를 선택
for (int i = 1; i < arr.Length; i++)
{
    // 현재 선택된 요소
    int current = arr[i];

    // 내부 반복문: 현재 선택된 요소를 이미 정렬된 부분과 비교하여 적절한 위치에 삽입
    int j = i - 1;
    while (j >= 0 && arr[j] > current)
    {
        arr[j + 1] = arr[j];
        j--;
    }

    // 삽입 위치에 현재 선택된 요소 삽입
    arr[j + 1] = current;
}

// 정렬된 배열 출력
foreach (int num in arr)
{
    Console.WriteLine(num);
}

 

// 초기 배열: {5, 2, 4, 6, 1, 3}

 

// 삽입 정렬 알고리즘 설명:

외부 반복문은 배열의 각 요소를 선택하는 역할. 시작은 두 번째 요소부터

내부 반복문은 현재 선택된 요소를 이미 정렬된 부분과 비교하여 적절한 위치에 삽입

선택된 요소보다 큰 값을 갖는 요소들을 오른쪽으로 이동시키면서 삽입 위치를 찾는다..

 

// 삽입 과정 설명:

현재 선택된 요소를 current에 저장.

내부 반복문에서 current와 비교하여 큰 값을 오른쪽으로 이동

적절한 위치를 찾으면 해당 위치에 current를 삽입

 

// 정렬 후 배열: {1, 2, 3, 4, 5, 6}

 

// 결과 출력:

foreach 루프를 사용하여 정렬된 배열을 출력

 

 

4) 퀵 정렬 ( Quick Sort )

퀵 정렬은 피벗을 기준으로 작은 요소들은 왼쪽, 큰 요소들은 오른쪽으로 분할하고 이를 재귀적으로 정렬하는 방법

시간 복잡도: 최악의 경우 O(n^2), 하지만 평균적으로 O(n log n)

공간 복잡도: 평균적으로 O(log n), 최악의 경우 O(n) (재귀 호출에 필요한 스택 공간)

 

간단 예시

public class QuickSort
{
    public static void Main()
    {
        int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };

        // 퀵 정렬 호출
        QuickSortAlgorithm(arr, 0, arr.Length - 1);

        // 정렬된 배열 출력
        foreach (int num in arr)
        {
            Console.WriteLine(num);
        }
    }

    public static void QuickSortAlgorithm(int[] arr, int low, int high)
    {
        if (low < high)
        {
            // 분할 작업: partitionIndex를 기준으로 배열을 분할하고 partitionIndex를 반환
            int partitionIndex = Partition(arr, low, high);

            // 분할된 부분 배열에 대해 재귀적으로 퀵 정렬 수행
            QuickSortAlgorithm(arr, low, partitionIndex - 1);
            QuickSortAlgorithm(arr, partitionIndex + 1, high);
        }
    }

    public static int Partition(int[] arr, int low, int high)
    {
        // 피벗 선택 (여기서는 가장 오른쪽의 요소를 선택)
        int pivot = arr[high];

        // 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 이동
        int i = low - 1;
        for (int j = low; j < high; j++)
        {
            if (arr[j] <= pivot)
            {
                i++;
                Swap(arr, i, j);
            }
        }

        // 피벗 위치를 바꾸어 줌
        Swap(arr, i + 1, high);

        // 피벗의 최종 위치를 반환
        return i + 1;
    }

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

 

// 퀵 정렬(Quick Sort)은 분할 정복(divide and conquer) 알고리즘의 하나로, 배열을 분할하고 각 부분을 독립적으로 정렬

 

// 초기 배열: {5, 2, 4, 6, 1, 3}

 

// 퀵 정렬 알고리즘 설명:

QuickSortAlgorithm 메서드가 퀵 정렬을 호출하고 각 부분을 정렬

Partition 메서드가 배열을 분할하고 피벗의 최종 위치를 반환.

Swap 메서드는 배열 내에서 요소의 위치를 교환

 

// 퀵 정렬 수행 과정:

배열이 분할되고, 각 부분 배열이 정렬되며, 이를 재귀적으로 반복

 

// 정렬 후 배열: {1, 2, 3, 4, 5, 6}

 

// 결과 출력:

정렬된 배열을 출력합니다.

 

 

5) 병합 정렬 ( Merge Sort )

병합 정렬은 배열을 반으로 나누고, 각 부분을 재귀적으로 정렬한 후, 병합하는 방법

시간 복잡도: 모든 경우에 대해 O(n log n)

공간 복잡도: O(n) (정렬을 위한 임시 배열이 필요함)

 

간단 예제

public class MergeSort
{
    public static void Main()
    {
        int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };

        // 병합 정렬 호출
        MergeSortAlgorithm(arr, 0, arr.Length - 1);

        // 정렬된 배열 출력
        foreach (int num in arr)
        {
            Console.WriteLine(num);
        }
    }

    public static void MergeSortAlgorithm(int[] arr, int left, int right)
    {
        if (left < right)
        {
            // 배열을 반으로 나누는 중간 지점 계산
            int mid = (left + right) / 2;

            // 왼쪽 부분 배열 정렬
            MergeSortAlgorithm(arr, left, mid);

            // 오른쪽 부분 배열 정렬
            MergeSortAlgorithm(arr, mid + 1, right);

            // 정렬된 부분 배열을 병합
            Merge(arr, left, mid, right);
        }
    }

    public static void Merge(int[] arr, int left, int mid, int right)
    {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // 임시 배열 생성
        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        // 왼쪽과 오른쪽 부분 배열로 값 복사
        for (int i = 0; i < n1; i++)
            leftArray[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
            rightArray[j] = arr[mid + 1 + j];

        // 병합
        int k = left;
        int p = 0, q = 0;

        while (p < n1 && q < n2)
        {
            if (leftArray[p] <= rightArray[q])
            {
                arr[k] = leftArray[p];
                p++;
            }
            else
            {
                arr[k] = rightArray[q];
                q++;
            }
            k++;
        }

        // 나머지 요소들 복사
        while (p < n1)
        {
            arr[k] = leftArray[p];
            p++;
            k++;
        }

        while (q < n2)
        {
            arr[k] = rightArray[q];
            q++;
            k++;
        }
    }
}

 

// 병합 정렬(Merge Sort)은 분할 정복(divide and conquer) 알고리즘

배열을 반으로 나눈 후 각각을 재귀적으로 정렬하고, 정렬된 부분 배열을 병합하여 전체 배열을 정렬

 

// 초기 배열: {5, 2, 4, 6, 1, 3}

 

// 병합 정렬 알고리즘 설명:

MergeSortAlgorithm 메서드가 배열을 반으로 나누고 각 부분을 정렬한 후 병합

Merge 메서드가 정렬된 부분 배열을 병합하여 정렬된 배열을 생성

 

// 병합 과정 설명:

배열을 반으로 나누어 각각을 정렬하고, 그 결과를 병합하여 최종적으로 정렬된 배열을 얻는다.

Merge 메서드에서는 두 개의 부분 배열을 비교하여 병합

 

// 정렬 후 배열: {1, 2, 3, 4, 5, 6}

 

// 결과 출력:

정렬된 배열을 출력

 

C# Sort

1) Sort 메서드

Sort 메서드는 배열이나 리스트의 요소들을 정렬하는 메서드

정렬은 오름차순으로 수행되며, 요소들의 자료형에 따라 다양한 정렬 기준을 사용할 수 있다.

Sort 메서드는 원래의 배열이나 리스트를 직접 수정하므로 반환값이 없다.

 

사용 예제

// 정수 배열 정렬 예제
int[] numbers = { 5, 2, 8, 3, 1, 9, 4, 6, 7 };
Array.Sort(numbers);
Console.WriteLine(string.Join(", ", numbers));

// 문자열 리스트 정렬 예제
List<string> names = new List<string> { "John", "Alice", "Bob", "Eve", "David" };
names.Sort();
Console.WriteLine(string.Join(", ", names));

 

간단 예시

using System;

public class SortingExample
{
    public static void Main()
    {
        // 정렬할 배열
        int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };

        // 배열을 정렬 (오름차순 정렬)
        Array.Sort(arr);

        // 정렬된 배열 출력
        Console.WriteLine("오름차순 정렬:");
        foreach (int num in arr)
        {
            Console.Write(num + " ");
        }

        // 내림차순 정렬을 위해 비교자(Comparer) 사용
        Array.Sort(arr, (a, b) => b.CompareTo(a));

        // 정렬된 배열 출력
        Console.WriteLine("\n내림차순 정렬:");
        foreach (int num in arr)
        {
            Console.Write(num + " ");
        }
    }
}

 

// C#의 Sort 메서드는 배열의 요소를 정렬하는데 사용

이 메서드는 .NET Framework의 Array 클래스에 속해 있다.

 

// 초기 배열: {5, 2, 4, 6, 1, 3}

 

// 오름차순 정렬:

Array.Sort(arr)를 사용하여 배열을 오름차순으로 정렬

기본적으로 오름차순 정렬이 적용

 

// 오름차순 정렬 결과:

1 2 3 4 5 6와 같이 출력

 

// 내림차순 정렬:

람다식을 사용하여 내림차순으로 정렬.

Array.Sort(arr, (a, b) => b.CompareTo(a))에서 b.CompareTo(a)는

역순으로 정렬하기 위한 비교자

 

// 내림차순 정렬 결과:

6 5 4 3 2 1과 같이 출력됩니다.