정렬 알고리즘

1. 정렬의 개념 (Sorting Concept)

정렬(Sorting)은 데이터를 특정 순서에 따라 재배열하는 과정입니다. 데이터 처리 및 분석에서 매우 기본적인 작업입니다.

• 정의: 데이터에 대하여 오름차순 또는 내림차순으로 재배열함
• 오름차순(Ascending Order): 작은 것 → 큰 것 (예: 1, 2, 3, 4, 5...)
• 내림차순(Descending Order): 큰 것 → 작은 것 (예: 10, 9, 8, 7...)

정렬 알고리즘을 이해하기 전, 배열 처리 및 값 교환(SWAP) 알고리즘에 대한 이해가 필수적입니다.

1.1. 배열 처리 (Array Handling)

C 언어에서 함수를 통해 배열을 처리하는 기본적인 방법:

• 배열 출력 예시:

  void printArr(int arr[], int n) {
    for (int i = 0; i < n; i++) {
      printf("%d ", arr[i]);
    }
    printf("\n");
  }

• 배열 내 최댓값 찾기:

  int MaxArr(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
      if (arr[i] > max) max = arr[i];
    }
    return max;
  }

1.2. 교환 (SWAP) 알고리즘

정렬 알고리즘에서 두 변수의 값을 서로 바꾸는 SWAP 알고리즘은 핵심입니다.

• 원리:

  int temp = a;
  a = b;
  b = temp;

• 함수를 이용한 SWAP

  • 값에 의한 호출(Call by Value):

    void swap(int n1, int n2) {
      int temp = n1;
      n1 = n2;
      n2 = temp;
    }
    // 원본 변수에는 영향 없음
  • 주소에 의한 호출(Call by Reference):

    void swap(int *n1, int *n2) {
      int temp = *n1;
      *n1 = *n2;
      *n2 = temp;
    }
    // 원본 변수 값이 바뀜

---

2. 다양한 정렬의 종류 (Types of Sorting Algorithms)

대표적인 세 가지 정렬 알고리즘(오름차순 기준): 선택 정렬, 버블 정렬, 삽입 정렬

2.1. 선택 정렬 (Selection Sort)

• 정의: 기준 위치의 값(i)과 나머지 배열의 값들을 비교하며 교환

• 동작 원리:

  • i=0부터 N-2까지, i+1~N-1 중 최솟값을 찾아 i와 교환

• 코드 예시:

  for (int i = 0; i < N - 1; i++) {
    int min = i;
    for (int j = i + 1; j < N; j++) {
      if (arr[j] < arr[min]) min = j;
    }
    swap(&arr[i], &arr[min]);
  }

2.2. 버블 정렬 (Bubble Sort)

• 정의: 인접한 두 요소를 비교하여 정렬 순서에 맞지 않으면 교환, 가장 큰(작은) 요소를 끝으로 이동

• 동작 원리:

  • N-11까지, 0i-1 인접 요소 비교/교환

• 코드 예시:

  for (int i = N - 1; i > 0; i--) {
    for (int j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(&arr[j], &arr[j + 1]);
      }
    }
  }

2.3. 삽입 정렬 (Insertion Sort)

• 정의: 두 번째 요소부터 시작, 각 요소를 이미 정렬된 부분의 올바른 위치에 삽입

• 동작 원리:

  • i=1~N-1, key값을 앞쪽 정렬된 부분과 비교하며 삽입

• 코드 예시:

  for (int i = 1; i < N; i++) {
    int key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }

---

결론

이 자료는 C 언어를 활용한 정렬 알고리즘의 기초를 다루며, 정렬의 개념과 필수적인 SWAP 알고리즘을 설명합니다.
선택 정렬, 버블 정렬, 삽입 정렬의 원리와 구현 예시를 통해 정렬의 기본 메커니즘을 쉽게 이해할 수 있습니다.
각 알고리즘은 오름차순 정렬을 기준으로 설명되며, C 코드 스니펫과 단계별 실행 과정을 통해 구체적인 동작 방식을 파악할 수 있습니다.