C# 버블, 선택, 삽입, 퀵 정렬 예시 간단 구현

버블 정렬

인접한 두 원소를 비교하여 정렬하는 알고리즘

만약 더 작은 원소가 오른쪽에 있다면, 두 원소를 교환합니다. 이런 식으로 배열의 끝까지 진행하면 가장 큰 원소가 가장 오른쪽으로 이동하게 됩니다.

 

• 코드 작성

public static void BubbleSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                // 인접한 요소를 교환
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

 

 

선택 정렬

주어진 배열에서 가장 작은 원소를 선택하여 정렬하는 알고리즘

선택한 원소를 배열의 맨 앞 또는 맨 뒤로 옮기고, 나머지 부분에서 동일한 과정을 반복합니다.

 

• 코드 작성

public static void SelectionSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 0; i < n - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[minIndex])
            {
                // 최소값을 찾음
                minIndex = j;
            }
        }
        // 최소값과 현재 요소를 교환
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

 

 

삽입 정렬

배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 원소를 정렬된 부분으로 삽입하는 알고리즘입니다.

 

• 코드 작성

public static void InsertionSort(int[] arr)
{
    int n = arr.Length;
    for (int i = 1; i < n; i++)
    {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key)
        {
            // 삽입할 위치를 찾아 요소를 이동
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

 

 

퀵 정렬

배열을 분할하고 각 부분을 재귀적으로 정렬하는 방식으로 동작합니다. 

 

• 코드 작성

public static void QuickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
        int pivot = Partition(arr, low, high);

        QuickSort(arr, low, pivot - 1);
        QuickSort(arr, pivot + 1, high);
    }
}

private 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++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    int swap = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = swap;

    return i + 1;
}