[C#] 알고리즘 1 (정렬)

정렬 알고리즘

---

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

선택 정렬 ( Selection Sort )

• 선택 정렬은 배열에서 최소값(또는 최대값)을 찾아 맨 앞(또는 맨 뒤)와 교환하는 방법.
• 시간 복잡도: 최악의 경우와 평균적인 경우 모두 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;
    
      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);
  }
  

삽입 정렬 ( Insertion Sort )

• 삽입 정렬은 정렬되지 않은 부분에서 요소를 가져와 정렬된 부분에 적절한 위치에 삽입하는 방법이다.
• 시간 복잡도: 최악의 경우 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++)
  {
      int j = i - 1;
      int key = arr[i];
    
      while (j >= 0 && arr[j] > key)
      {
          arr[j + 1] = arr[j];
          j--;
      }
    
      arr[j + 1] = key;
  }
    
  foreach (int num in arr)
  {
      Console.WriteLine(num);
  }
  

퀵 정렬 ( Quick Sort )

• 퀵 정렬은 피벗을 기준으로 작은 요소들은 왼쪽, 큰 요소들은 오른쪽으로 분할하고 이를 재귀적으로 정렬하는 방법.
• 시간 복잡도: 최악의 경우 O(n^2), 하지만 평균적으로 O(n log n)
• 공간 복잡도: 평균적으로 O(log n), 최악의 경우 O(n) (재귀 호출에 필요한 스택 공간)

  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;
  }
    
  int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };
    
  QuickSort(arr, 0, arr.Length - 1);
    
  foreach (int num in arr)
  {
      Console.WriteLine(num);
  }
    
  

병합 정렬 ( Merge Sort )

• 병합 정렬은 배열을 반으로 나누고, 각 부분을 재귀적으로 정렬한 후, 병합하는 방법이다.
• 시간 복잡도: 모든 경우에 대해 O(n log n)
• 공간 복잡도: 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);
  
    foreach (int num in arr)
    {
        Console.WriteLine(num);
    }