선택 정렬

출처: https://jongmin92.github.io/2017/11/06/Algorithm/Concept/basic-sort/

기본적인 정렬 알고리즘 (선택, 삽입, 버블)

 

#include <iostream>

using namespace std;

void print_arr(int a[], int size) {
    for (int i = 0; i < size; i++) {
        cout << a[i] << ' ';
    }
    cout << '\n';
}

void selection_sort(int a[], int size) {
    int min_idx, tmp;

    for (int i = 0; i < size - 1; i++) {
        min_idx = i;
        for (int j = i + 1; j < size; j++) {
            if (a[j] < a[min_idx]) {
                min_idx = j;
            }
        }
        tmp = a[min_idx];
        a[min_idx] = a[i];
        a[i] = tmp;
    }
}

int main() {
    int a[] = { 15, 2, 24, 18, 7, 13, 12, 4, 21, 9 };
    int size = sizeof(a) / sizeof(int);
    print_arr(a, size);
    selection_sort(a, size);
    print_arr(a, size);
    return 0;
}

 

핵심은 요부분

for (int i = 0; i < size - 1; i++) {
        min_idx = i;
        for (int j = i + 1; j < size; j++) {
            if (a[j] < a[min_idx]) {
                min_idx = j;
            }
        }
        tmp = a[min_idx];
        a[min_idx] = a[i];
        a[i] = tmp;
    }

if문을 이렇게 이해하자.

a[j] < a[min_idx] 

최솟값우선정렬이니 min_idx가 기준이 된다.

 

-min_idx 기준-

나는 처음 인덱스로 min_idx를 가져갈게 나보다 작은 배열값이 있으면(if문) 그 인덱스를 내 걸로 할게.

비교하고 작은 거 가지고 또 비교하고 작은 거 가지고

 

그렇게해서 첫 루프(i)에서 가장 작은 배열값을 가진 인덱스를 min_idx가 갖게 된다.

tmp에 min_idx를 인덱스로 가진 배열값(최솟값)을 넣고 최솟값을 가지는 인덱스(min_idx)가 있던 자리에는 a[i]가 들어간다.

마지막으로 a[i]에 최솟값을 넣어준다.

i는 차피 오름차순으로 커질테니 배열의 왼쪽부터 차례대로 작은값이 들어간다.

 

#include <iostream>

using namespace std;

int main(void)
{
  int i,j,min,idx,tmp;
  int arr[10]={1,5,4,3,7,9,10,8,6,2};
  
  for(i=0; i<10; i++){
    min=9999;
    for(j=i; j<10; j++){
      if(min>arr[j]){
        min=arr[j];
        idx=j;
      }   
    }
    tmp=arr[i];
    arr[i]=arr[idx];
    arr[idx]=tmp;
  }
  for(i=0; i<10; i++){
    cout<<arr[i]<<' ';
  }
}

// 선택정렬의 핵심은 주어진 숫자에서 검사하면서 하나씩 검사범위가 줄어드는 것을 생각
// 2중 for문 안의 인자가 시작점이 j=i 를 꼭 기억!