C언어 학습 노트 : 9. 배열 활용 프로그래밍#

1. 정렬 알고리즘#

(1) 버블 정렬 (Bubble Sort)#

• 인접한 두 원소를 비교하여 필요할 때마다 교환한다.
• 한 번의 반복이 끝나면 가장 큰 원소가 배열의 끝으로 이동한다.
• 마치 거품이 위로 올라가듯 큰 값이 뒤쪽으로 모인다.
• 시간 복잡도: O(n²)

(2) 선택 정렬 (Selection Sort)#

• 배열에서 최소(또는 최대) 원소를 찾아 맨 앞(또는 맨 뒤)과 교환한다.
• 한 번의 반복에서 교환은 한 번만 이루어진다.
• 구현이 단순하나, 역시 O(n²) 시간 복잡도를 가진다.

(3) 효율성 비교#

• 두 알고리즘 모두 구현이 쉽지만, 데이터 크기가 커질수록 비효율적이다.
• 실제로는 퀵정렬, 병합정렬, 힙정렬과 같은 알고리즘이 더 적합하다.

2. 배열을 활용한 핵심 프로그래밍 기법#

(1) 보수를 이용한 인덱스 전개#

• 역순으로 접근할 때 arr[n-1-j] 형태로 작성한다.
• 예: 12345 → 54321 변환 시 arr[n-1-j]를 활용.

(2) Flag 기법#

• flag 변수를 두어 흐름을 제어한다.

• 예:

  int flag = 1;
  if (flag) {
      // 실행 1
  } else {
      // 실행 2
  }
  flag = -flag; // 상태 전환
  

• 반복적으로 상태를 바꾸며 실행 흐름을 제어할 수 있다.

(3) Direction 기법#

• 방향을 나타내는 변수를 두어 인덱스 이동을 제어한다.
• direction = 1 → 증가 방향
• direction = -1 → 감소 방향
• 반복문 안에서 index += direction; 형태로 사용 가능하다.

학습 포인트 정리#

• 버블 정렬은 인접 원소를 계속 교환하여 큰 값이 뒤로 이동한다.
• 선택 정렬은 최소값(또는 최대값)을 찾아 한 번만 교환한다.
• 두 정렬 모두 O(n²) 시간 복잡도로, 데이터가 많아지면 비효율적이다.
• 배열 프로그래밍에서는 역방향 인덱싱, flag 토글, 방향 변수 제어 등 다양한 기법이 활용된다.