c언어 - 선택 정렬 (Selection Sort)

선택 정렬은 기준점을 잡고 처음부터 끝까지 비교 후 가장 작은 값을 바꾸는 정렬이다.

 

순차 정렬, 버블 정렬, 선택 정렬 세 정렬은 코드는 단순하나 컴퓨터 입장에서 비효율 적이여서 싫어하는 정렬이다. 비교대상이 30개 미만일 경우 사용하기에 좋다.

 

비교 횟수는 n-1 -> n-2 -> n-3 -> ... -> n-n+3 -> n-n+2 -> n-n-1 순으로 값이 줄어들며 비교된다.

 

비교하는 값은 노란색

정렬후 값은 보라색

 

 

 

 

---

핵심 알고리즘

---

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

 

코드

---

include <stdio.h>

void SelectionSort(int *arr, int n, int i, int j);
void printarr(int *arr, int n, int i, int j);
void swap(int *a,int *b);

int main(){
  int arr[] = {7,2,4,8,6};
  SelectionSort(arr,5,0,0);

  return 0;
}

void SelectionSort(int *arr,int n, int i, int j){
    int min;
    printarr(arr, n, -5, 5);
    for(i=0; i<n-1; i++){
        min = i;
        for(j=i+1; j<n; j++){
            if(arr[min] > arr[j])
                min = j;
        printarr(arr, n, i, j);
        }
        if(min != i)
            swap(&arr[i],&arr[min]);
    }
  printarr(arr, n, n, -2);
}

void printarr(int *arr, int n, int i, int j) {
    int text=0;
    for(int c = 0; c<n; c++) {
        if ( c < i) {
            printf("\x1b[35m");
        }
        else if ( c == j || c == i) {
            printf("\x1b[33m");
        }
        else{
            printf("\x1b[37m");
        }
        printf(" %d ", arr[c]);
    }
    printf("\n");
}

void swap(int *a,int *b) {
    int t;
    t = *a;
    *a = *b;
    *b = t;
}