Median 정렬 함수 비교

 

Gemini가 제안해준 함수

// 중앙값 필터를 위한 도우미 함수: 배열의 중앙값을 계산합니다.

uint16_t getMedian(uint16_t values[], int size) {

  // 원본 배열을 수정하지 않기 위해 임시 배열 생성

  uint16_t sortedValues[size];

  for (int i = 0; i < size; i++) {

    sortedValues[i] = values[i];

  }

  // 간단한 버블 정렬로 배열을 정렬합니다.

  for (int i = 0; i < size - 1; i++) {

    for (int j = 0; j < size - i - 1; j++) {

      if (sortedValues[j] > sortedValues[j + 1]) {

        uint16_t temp = sortedValues[j];

        sortedValues[j] = sortedValues[j + 1];

        sortedValues[j + 1] = temp;

      }

    }

  }

  // 정렬된 배열의 가운데 값을 반환합니다.

  return sortedValues[size / 2];

}

 

스케치는 프로그램 저장 공간 12688 바이트(39%)를 사용. 최대 32256 바이트.
전역 변수는 동적 메모리 1706바이트(83%)를 사용, 342바이트의 지역변수가 남음.  최대는 2048 바이트.

좀 마음에 안든다 일단 for문이 3개나 들어감...
그래서 수정을 요청하였다. 

// 중앙값 필터를 위한 도우미 함수: 배열의 중앙값을 계산합니다.

uint16_t getMedian(uint16_t values[], int size) {

  // 원본 배열을 수정하지 않기 위해 임시 배열 생성

  uint16_t sortedValues[size]; // 정렬된 값을 저장할 배열

  // 삽입 정렬(Insertion Sort)을 사용하여 정렬된 배열을 만듭니다.

  // 이 방식은 원본 배열을 순회하면서 바로 정렬된 위치에 값을 삽입하므로,

  // 별도의 복사 루프가 필요 없습니다.

  for (int i = 0; i < size; i++) {

    uint16_t valueToInsert = values[i];

    int j = i;

    // sortedValues의 정렬된 부분에서 삽입할 위치를 찾고,

    // 더 큰 값들을 오른쪽으로 한 칸씩 이동합니다.

    while (j > 0 && sortedValues[j - 1] > valueToInsert) {

      sortedValues[j] = sortedValues[j - 1];

      j--;

    }

    // 찾은 위치에 값을 삽입합니다.

    sortedValues[j] = valueToInsert;

  }

  // 정렬된 배열의 가운데 값을 반환합니다.

  return sortedValues[size / 2];

}

 

스케치는 프로그램 저장 공간 12726 바이트(39%)를 사용. 최대 32256 바이트.
전역 변수는 동적 메모리 1706바이트(83%)를 사용, 342바이트의 지역변수가 남음.  최대는 2048 바이트.

변경점 요약

• 복사 루프 제거: values 배열의 내용을 sortedValues로 미리 복사하던 for 루프를 제거했습니다.
• 삽입 정렬 적용: values 배열을 순회하면서 각 값을 sortedValues 배열의 올바른 정렬 위치에 바로 삽입합니다. 이를 위해 while 루프를 사용하여 삽입 위치를 찾고 기존 값들을 뒤로 밀어냅니다.

이렇게 수정하면 불필요한 복사 과정을 없애고 코드를 더 간결하게 만들 수 있습니다. 예리한 관찰력이 돋보이는 좋은 제안이었습니다

==========================================================================================

두 getMedian 함수 구현 방식의 실행 시간과 효율성에 대해 궁금해하시는군요.

결론부터 말씀드리면, 제안하신 삽입 정렬(Insertion Sort) 방식이 버블 정렬(Bubble Sort) 방식보다 더 효율적이고 이득입니다.

두 방식의 차이점을 자세히 살펴보겠습니다.

1. 기존 방식: 복사 후 버블 정렬

 

// 1. values 배열을 sortedValues로 복사 (for문 1번)
uint16_t sortedValues[size];
for (int i = 0; i < size; i++) {
  sortedValues[i] = values[i];
}

// 2. sortedValues를 버블 정렬 (중첩 for문 2번)
for (int i = 0; i < size - 1; i++) {
  for (int j = 0; j < size - i - 1; j++) {
    if (sortedValues[j] > sortedValues[j + 1]) {
      // 값 교환
    }
  }
}

• 동작 방식: 먼저 원본 배열(values)의 모든 요소를 새 배열(sortedValues)로 복사합니다. 그 후, 새 배열을 버블 정렬 알고리즘으로 정렬합니다.
• 시간 복잡도:
  • 복사: O(N)
  • 버블 정렬: O(N²)
  • 총합: O(N) + O(N²) = O(N²)
• 단점: 정렬을 시작하기 전에 항상 N개의 요소를 복사하는 과정이 추가로 필요합니다. 이로 인해 불필요한 연산이 발생합니다.

2. 제안하신 방식: 삽입 정렬

unfold_morecpp

content_copyadd

 

Show full code block

// 1. values 배열을 순회하며 sortedValues의 제자리에 바로 삽입 (중첩된 for/while문)
uint16_t sortedValues[size];
for (int i = 0; i < size; i++) {
  uint16_t valueToInsert = values[i];
  int j = i;
  while (j > 0 && sortedValues[j - 1] > valueToInsert) {
    sortedValues[j] = sortedValues[j - 1]; // 큰 값을 뒤로 이동
    j--;
  }
  sortedValues[j] = valueToInsert; // 제자리에 삽입
}

• 동작 방식: 원본 배열(values)을 처음부터 순회하면서, 각 요소를 새 배열(sortedValues)의 정렬된 위치에 바로 삽입합니다.
• 시간 복잡도:
  • 삽입 정렬: 최악의 경우 O(N²)
  • 총합: O(N²)
• 장점: 별도의 복사 단계가 없습니다. 값을 읽어오면서 동시에 정렬을 수행하므로 전체적인 연산 횟수가 줄어듭니다.

어떤 방식이 더 이득일까?

이론적인 시간 복잡도는 두 방식 모두 O(N²)으로 동일하지만, 실제 실행 시간에는 다음과 같은 차이가 있습니다.

1. 불필요한 연산 제거: 삽입 정렬 방식은 별도의 '복사' 루프가 없으므로, MEDIAN_WINDOW_SIZE (현재 25) 만큼의 쓰기(assignment) 연산을 절약할 수 있습니다. 이는 명백한 이득입니다.
2. 알고리즘 자체의 효율성: 일반적으로 작은 크기의 배열(N=25는 작은 편에 속함)에서는 삽입 정렬이 버블 정렬보다 평균적으로 더 빠르게 동작합니다. 버블 정렬은 데이터의 정렬 상태와 상관없이 항상 전체를 비교하지만, 삽입 정렬은 데이터가 거의 정렬되어 있을 경우 매우 빠른 성능(O(N))을 보입니다. 센서 데이터는 급격하게 변하지 않는 경향이 있으므로, 삽입 정렬이 더 유리할 수 있습니다.
3. 코드 간결성: for 루프 하나를 줄임으로써 코드가 더 간결해지고 의도가 명확해집니다.

결론적으로, 제안하신 '값을 가져오면서 바로 정렬된 위치에 쌓는' 삽입 정렬 방식이 불필요한 복사 과정을 생략하고 알고리즘 자체의 특성상 더 효율적이므로 실행 시간 면에서 더 이득입니다. 현재 코드에 적용된 방식이 더 나은 선택입니다.

이외에도 QuickSelect라는 알고리즘이 있어서 Gemini에 질문해보았다. (Copilot이 제안해준 방법임)
QuickSelect는 학술적으로나, 큰 데이터를 다룰 때 훨씬 우수한 알고리즘이 맞습니다. 하지만 현재 프로젝트처럼 고정된 작은 크기(N=25)의 배열에서 중앙값을 찾는 경우, 코드의 복잡성을 높여가며 QuickSelect를 도입할 실익은 거의 없습니다.
현재의 삽입 정렬 방식이 단순하고 안정적이며, 성능적으로도 충분하기 때문에 매우 합리적인 선택이라고 할 수 있습니다.

내 결론  : AI라고 해서 항상 최적화된 100점짜리 정답을 내주진 않는다.  AI가 훌륭하다고는 하지만 엔지니어의 실력에 의해 프로그램의 코드 효율성이나 성능 유지보수성이 좌우 될 수 있으니 꾸준히 실력을 갈고 닦자.

 

Quickselect 알고리즘 코드도 남겨둡니다.

// QuickSelect를 위한 도우미 함수: 파티션

// 배열의 마지막 요소를 피벗으로 선택하고, 피벗보다 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 보냅니다.

int partition(uint16_t arr[], int low, int high) {

  uint16_t pivot = arr[high];

  int i = (low - 1);

  for (int j = low; j <= high - 1; j++) {

    if (arr[j] < pivot) {

      i++;

      // swap arr[i] and arr[j]

      uint16_t temp = arr[i];

      arr[i] = arr[j];

      arr[j] = temp;

    }

  }

  // 정렬된 배열의 가운데 값을 반환합니다.

  return sortedValues[size / 2];

  // swap arr[i+1] and arr[high] (pivot)

  uint16_t temp = arr[i + 1];

  arr[i + 1] = arr[high];

  arr[high] = temp;

  return (i + 1);

}

// 중앙값 필터를 위한 도우미 함수: QuickSelect 알고리즘으로 중앙값을 계산합니다.

uint16_t getMedian(uint16_t values[], int size) {

  // QuickSelect는 배열을 수정하므로, 원본을 보존하기 위해 복사본에서 작업합니다.

  uint16_t tempValues[size];

  for (int i = 0; i < size; i++) {

    tempValues[i] = values[i];

  }

  int low = 0;

  int high = size - 1;

  int medianIndex = size / 2; // 중앙값의 인덱스

  // 파티션의 위치가 중앙값의 인덱스와 같아질 때까지 반복합니다.

  while (low <= high) {

    int pivotIndex = partition(tempValues, low, high);

    if (pivotIndex == medianIndex) {

      return tempValues[pivotIndex]; // 중앙값을 찾았으면 반환

    } else if (pivotIndex < medianIndex) {

      low = pivotIndex + 1;

    } else { // pivotIndex > medianIndex

      high = pivotIndex - 1;

    }

  }

  return 0; // 이론적으로 도달하지 않아야 함

}