정렬 알고리즘

Stable 과 In-place 정리

Stable

크기가 같은 데이터가 정렬 후에도 입력 순서 유지

stable : 5 5 —(정렬 이후)— 5 5

not-stable : 5 5 —(정렬 이후)— 5 5

In-place

입력 데이터를 저장하는 메모리 외에는 상수 크기의 메모리만 필요

입력 데이터 크기 : n

[알고리즘] 기본 정렬 알고리즘 비교| stable vs not stable| in-place vs not in-place | 선택 정렬(selection sort), 버블 정렬(bubble sort), 삽입 정렬(insertion sort), 합병 정렬(merge sort), 퀵 정렬(quick sort)

---

Sort Algorithm

• Selection sort (선택 정렬)
• Bubble sort (버블 정렬)
• Insertion sort (삽입 정렬)
• Merge sort (합병 정렬)
• Quick sort (퀵 정렬)

---

Selection sort (선택 정렬)

정렬 과정에서 데이터가 정렬된 데이터(왼쪽)와 정렬되지 않은 데이터(오른쪽)로 나뉘어짐

• 특징

  • not-stable
  • In-place

• 로직

  1. 오른쪽 데이터에서 제일 작은 데이터를 찾아서 선택
  2. 해당 숫자와 오른쪽 데이터의 첫번째 인덱스와 swap

https://hyo-ue4study.tistory.com/68

• 코드

  • 정렬하시오

    void selectionSort(int *arr, int n)
    {
        for (int i = 0; i < n; i++)
        {
            int minIdx = i;
    
            // 정렬되지 않은 데이터들(i+1 ~ n)
            for (int j = i + 1; j < n; j++)
            {
                if (arr[j] < arr[minIdx])
                    minIdx = j;
            }
    				// 자기 자신이 최소일 경우 swap 하지 않음 : 없어도 노상관
    				if (minIdx != i)
                swap(arr[i], arr[minIdx]);
        }
    }

  • 정렬 시, swap한 횟수와 비교한 횟수를 구하시오

    • 전역변수 사용

      int swapCount, compareCount;
      
      void selectionSort(int *arr, int n)
      {
          for (int i = 0; i < n; i++)
          {
              int minIdx = i;
      
              // 정렬되지 않은 데이터들(i+1 ~ n)
              for (int j = i + 1; j < n; j++)
              {
                  compareCount++;
                  if (arr[j] < arr[minIdx])
                      minIdx = j;
              }
              if (minIdx != i)
              {
                  swap(arr[i], arr[minIdx]);
                  swapCount++;
              }
          }
      }

    • 구조체 사용

      struct Count
      {
          int swap = 0;
          int compare = 0;
      }; // struct(구조체) 작성 시, ; 쓰는 거 잊지 말기 !
      
      Count selectionSort(int *arr, int n)
      {
          Count count;
          for (int i = 0; i < n; i++)
          {
              int minIdx = i;
      
              // 정렬되지 않은 데이터들(i+1 ~ n)
              for (int j = i + 1; j < n; j++)
              {
                  count.compare++;
                  if (arr[j] < arr[minIdx])
                      minIdx = j;
              }
              if (minIdx != i)
              {
                  swap(arr[i], arr[minIdx]);
                  count.swap++;
              }
          }
          return count;
      }
      
      int main()
      /* 
      출력을 위한 코드 */
          Count counts;
          counts = selectionSort(numbers, n);
      /* 
      출력을 위한 코드 */
      }

---

Bubble sort (버블 정렬)

인접한 두 수의 크기 비교하여 swap하며 정렬(오름차순, 내림차순)

• Pass
  • 맨 왼쪽 인접한 두 수의 크기 비교하여 오른쪽 끝까지 정렬 진행
  • Pass의 결과 : 제일 큰 수가 맨 오른쪽 끝으로 이동 → 다음 Pass에서 제외

• 코드
  • 정렬
    • 일반 버블 정렬

      void bubbleSort(int *arr, int n)
      {
          for (int i = 0; i < n; i++)
          {
              for (int j = 1; j < n - i; j++)
              {
                  if (arr[j] < arr[j - 1])
                      swap(arr[j], arr[j - 1]);
              }
          }
      }

    • 성능 향상된 버블 정렬

      void impoveBubbleSort(int *arr, int n)
      {
          for (int pass = 0; pass < n; pass++)
          {
              bool swapped = false;
              for (int j = 1; j < n - pass; j++)
              {
                  if (arr[j] < arr[j - 1])
      						{
                      swap(arr[j], arr[j - 1]);
                      swapped = true;
                  }
              }
              if(!swapped)
                  break;
          }
      }

---