Algorithm(3): Selection Sort

선택정렬

#define MAX 100
void print_array(const int arr[], int length);
void swap(int*, int*);
void selection_sort(int arr[], int length);

int main()
{
  int i = 0, temp, data[MAX];
  printf("Enter integers seperated by a blank.\n");
  while (1)
  {
    scanf("%d", &temp);
    if (temp < 0)
      break;
    data[i++] = temp;
  }

  printf("Before sorting: ");
  print_array(data, i); //data 포인터 즉 포인터 시작주소
  printf("\n");

  selection_sort(data, i);
  printf("After sorting: ");
  print_array(data, i);
  printf("\n");

  return 0;
}

void print_array(const int arr[], int length)
{
  int i;
  for (i = 0; i< length; i++)
    printf("%d ", arr[i]);
}

void swap(int* p, int* q)
{
  int temp;
  temp = *p;
  *p = *q;
  *q = temp;
}

void selection_sort(int arr[], int length)
{
  int last, largest, current;

  for (last = length-1; last > 0; last--)
  {
    largest = 0; //일단 arr[0]이 제일 크다고 가정하는거다.
    for (current = 1; current <= last; current++)
    {
      if (arr[current] > arr[largest])
        largest = current;
    }
    swap(&arr[largest], &arr[last]);
  }
}

프로그램의 주요 기능
사용자 입력:

정수를 입력받아 배열 data에 저장합니다.
음수를 입력하면 입력이 종료됩니다.
정렬 전 배열 출력:

함수 print_array를 이용해 배열을 출력합니다.
선택 정렬 수행:

함수 selection_sort를 호출하여 배열을 오름차순으로 정렬합니다.
정렬 후 배열 출력:

다시 print_array를 호출해 정렬된 배열을 출력합니다.

핵심 아이디어:

• 배열의 끝부터 정렬합니다.
• 매번 가장 큰 값을 찾아 배열의 끝에 배치합니다.

동작 단계

동작 단계
배열이 [3, 1, 4, 1, 5]라고 가정하고 정렬 과정을 보겠습니다.

last = 4 (마지막 인덱스):

배열 범위 [3, 1, 4, 1, 5]에서 가장 큰 값 5를 찾습니다.
5와 마지막 값 5를 교환(사실상 교환 없음).
결과: [3, 1, 4, 1, 5].
last = 3:

배열 범위 [3, 1, 4, 1]에서 가장 큰 값 4를 찾습니다.
4와 마지막 값 1을 교환.
결과: [3, 1, 1, 4, 5].
last = 2:

배열 범위 [3, 1, 1]에서 가장 큰 값 3을 찾습니다.
3와 마지막 값 1을 교환.
결과: [1, 1, 3, 4, 5].
last = 1:

배열 범위 [1, 1]에서 가장 큰 값 1을 찾습니다.
1와 마지막 값 1을 교환(사실상 교환 없음).
결과: [1, 1, 3, 4, 5].
종료:
배열이 완전히 정렬되었습니다: [1, 1, 3, 4, 5].

시간복잡도

시간 복잡도:
최선, 평균, 최악 모두 O(n²)입니다.
이중 루프에서 기인한 계산 비용 때문입니다.

비효율적이지만 개념 이해에 필요합니다.