SelectionSort (선택 정렬)

선택 정렬이란, 배열에서 가장 작은 값을 찾아서 앞으로 가져오는 방식을 반복하는 정렬 방법입니다.

 

글로만 보면 이해가 안될수도 있으니 그림으로 살펴봅시다.

 

 

이렇게 가장 작은 수를 찾아서 정렬을 완료합니다.

 

 

 

코드)

#include <cassert>
#include <iostream>

bool CheckSorted(int* arr, int size);  // 정렬되었는지 확인할 함수
void PrintArr(int* arr, int size);     // 배열을 출력하는 함수

int main(void) {
  int arr[] = {8, 3, 2, 5, 1, 1, 2, 5, 8, 9};
  int size = sizeof(arr) / sizeof(int);
  assert(size > 0);  // 배열의 크기가 1보다 작으면 오류 발생하도록.

  int min_num = 1000;
  int min_index = 0;

  int index = 0;
  while (!CheckSorted(arr, size)) {  // 배열이 정렬될 때까지 반복
    for (int i = index; i < size; i++) {
      if (arr[i] <= min_num) {
        min_num = std::min(arr[i], min_num);
        min_index = i;
      }
    }
    std::swap(arr[index], arr[min_index]);  // 최솟값을 찾아 swap

    PrintArr(arr, size);  // 과정마다 출력하여 정렬되었는지 확인
    std::cout << std::boolalpha;
    std::cout << " -> " << CheckSorted(arr, size) << '\n';
    index++;
    min_num = arr[index];
  }

  return 0;
}

bool CheckSorted(int* arr, int size) {
  for (int i = 0; i < size - 1; i++) {
    if (arr[i] > arr[i + 1]) return false;
  }
  return true;
}

void PrintArr(int* arr, int size) {
  for (int i = 0; i < size; i++) {
    std::cout << arr[i] << " ";
  }
  std::cout << '\n';
}

이와 같이 정렬되는 과정과 정렬되었을 떄 true 를 출력하고 끝나는 것을 확인할 수 있다.

 

 

 

 

시간 복잡도)

그렇다면, 선택 정렬의 시간 복잡도는 어떻게 될까? 

직접 알아보도록 합시다.

#include <fstream>
#include <iostream>

int main(void) {
  std::ofstream ofile("Tc.txt");
  for (int size = 1; size < 10000; size++) {
    int count = 0;
    int* arr = new int[size];

    int min_num = 1000;
    int min_index = 0;

    for (int i = 0; i < size - 1; i++) {
      for (int j = i + 1; j < size; j++) {
        count++;
        if (arr[j] < arr[min_index]) {
          min_index = j;
        }
      }
      std::swap(arr[i], arr[min_index]);
    }
    ofile << size << " , " << count << '\n';

    delete[] arr;
  }
  ofile.close();
  return 0;
}

 

시간 복잡도를 알아보기 위해 최악의 경우까지 반복하도록 설정하였고 , 반복을 할 때 마다 count 변수가 1씩 증가하도록 하였습니다.

 

그리고 , 몇 번 반복되었는지를 Tc.txt 파일을 만들어 기록했습니다.

 

이를 엑셀에서 그래프로 나타내어 보면, 아래와 같은 그래프가 나옵니다.

 

지금은 size를 10000 만큼 설정해서 끊겨있지만, 저 형태로 쭉 올라가는 그래프입니다.

 

O(n^2)

 

 

 

 

 

정렬의 안정성)

정렬의 안정성이 뭔지 모르시는 분들도 꽤 많으실 겁니다.

저도 처음 들었으니까요 .. ..

#include <algorithm>
#include <cassert>
#include <iostream>

struct Element {
  int key;
  char value;
};

bool CheckSorted(Element* arr, int size);
void PrintArr(Element* arr, int size);

int main(void) {
  Element arr[] = {{2, 'a'}, {2, 'b'}, {1, 'c'}};
  int size = sizeof(arr) / sizeof(arr[0]);
  PrintArr(arr, size);

  int min_index;
  for (int i = 0; i < size - 1; i++) {
    min_index = i;
    for (int j = i + 1; j < size; j++) {
      if (arr[j].key < arr[min_index].key) {
        min_index = j;
      }
    }
    std::swap(arr[i], arr[min_index]);
    PrintArr(arr, size);
  }

  return 0;
}

bool CheckSorted(Element* arr, int size) {
  for (int i = 0; i < size - 1; i++) {
    if (arr[i].key > arr[i + 1].key) return false;
  }
  return true;
}

void PrintArr(Element* arr, int size) {
  for (int i = 0; i < size; i++) {
    std::cout << "{" << arr[i].key << ", " << arr[i].value << "} ";
  }
  std::cout << '\n';
}

 

이 코드를 보시면 이해가 되실겁니다.

 

같은 값이라도 고유 value 값이 있는데 정렬을 마쳤을 때 key 값 뿐 아니라 value 값까지 정렬이 되면 안정,

정렬이 되지 않으면 불안정 이라고 합니다.

 

위 코드를 실행시켜보면,

이런 결과가 나옵니다.

 

key 값을 정렬하는 과정에서 value 값의 순서도 바뀐 것을 확인할 수 있습니다.

 

이는 불필요한 움직임이 있었다는 의미이고, 따라서 안정적이라고 보기 어려운 정렬 방식입니다.