[자료구조/C++] 정렬(Sorting) : 선택정렬(Selection Sort)

전공 수업과 교안을 바탕으로 개인적으로 공부한 내용입니다. 공부 내용을 정리하는 과정에서 잘못된 정보가 있을 수 있으니, 참고용으로만 봐주시면 감사하겠습니다. 피드백은 언제든 환영입니다! 😊

---

✔️ 선택정렬 (Selection Sort)

선택정렬은 주어진 배열에서 첫번째 원소부터 마지막 원소까지 차례대로 기준이 되는 원소로 설정하고, 해당 원소의 다음 원소들 중 가장 작은 원소를 찾아 기준이 되는 원소와 교환하는 방식으로 정렬하는 알고리즘이다.

즉, 주어진 배열에서 가장 작은 원소 값을 찾고, 해당 원소를 배열의 처음 원소와 교환한다. 다음으로 남은 배열에서 가장 작은 원소를 찾아 다음 위치의 원소와 교환하며 이러한 과정을 배열의 마지막 원소까지 반복하면 된다.

 

예를 들어 {30, 20, 40, 10, 5, 10,30, 15} 로 구성된 배열 A가 있다고 하자.

배열 A를 선택정렬 하는 과정은 다음과 같다.

먼저 step 0에서 배열의 0번째 값인 30이 기준이 되고, 그 뒤에 있는 원소들 중 가장 작은 값인 5를 찾아 교환한다. 다음으로 step 1에서도 배열의 1번째 값인 20울 기준으로 하고, 그 뒤에 있는 원소들 중 가장 작은 값인 10을 찾아 교환한다. 마찬가지로 배열 A의 나머지 원소들도 동일한 과정을 진행하면 된다.

 

따라서 선택정렬을 코드를 구현하면 다음과 같다.

✔️ 구현 코드

#include <iostream>
using namespace std;

void Swap(int &a, int &b) {
  int tmp = a;
  a = b;
  b = tmp;
}

void InsertionSort(int A[], int n) {
  int i, j, minIdx;

  for (int i=0; i<n-1; i++) {
    minIdx = i;
    for (j=minIdx+1; j<n; j++){
      if (A[minIdx] > A[j]) {
        minIdx = j;
      }
    }

    if (minIdx != i) {
      Swap(A[i], A[minIdx]);
    }
  }
}

int main() {
  int A[] = {30, 20, 40, 10, 5, 10, 30, 15};
  int size = sizeof(A)/sizeof(A[0]);

  InsertionSort(A, size);

  for (int i = 0; i<size; i++) {
    cout << A[i] << " ";
  }
  cout << endl;
  return 0;
}