C언어 배열 정리

 

 

 

 

 

 

 

 

 

🌟 과제 42, 내림차순 데이터 집합에 대한 이진 탐색

① 이진 탐색이란?

• 이진 탐색은 정렬된 배열에서 특정 값을 찾는 효율적인 알고리즘이다. 배열을 반으로 나누어 가며 탐색 범위를 좁혀가는 반식으로 작동한다

 

② 일반적인 이진 탐색 VS 내림차순 이진 탐색

• 일반적인 이진 탐색: 오름차순 정렬된 배열에서 사용
• 내림차순 이진 탐색: 내림차순 정렬된 배열에서 사용

 

③ 동작 원리

• 배열의 중간 지점 확인
• 찾는 값과 중간값 비교
• 내림차순이므로, 찾는 값이 중간값보다 크면 왼쪽 절반 탐색
• 찾는 값이 중간값보다 작으면 오른쪽 절반 탐색
• 값을 찾을 때까지 반복

 

#include <stdio.h>

int main() {
    int target; // 찾으려는 값을 저장할 변수
    int data[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    int size = 10;  // 배열 크기
    int mid, high, low;
    
    // 초기값 설정 (이 부분이 중요!)
    low = 0;           // 시작 인덱스
    high = size - 1;   // 끝 인덱스 (9)
    
    printf("찾으려는 값을 입력하세요: ");
    scanf("%d", &target);
    
    // 반복문으로 계속 탐색 (이 부분이 빠져있었음!)
    while (low <= high) {
        mid = (low + high) / 2;  // 중간 인덱스 계산
        
        if (data[mid] == target) {
            printf("값 %d를 인덱스 %d에서 찾았습니다!\n", target, mid);
            return 0;  // 찾았으므로 프로그램 종료
        } 
        else if (data[mid] < target) { // 중간 값보다 타겟이 크면 왼쪽에 있어요
            high = mid - 1; // 탐색 범위를 왼쪽으로 좁혀요
        } 
        else { // data[mid] > target (중간 값보다 타겟이 작으면 오른쪽에 있어요)
            low = mid + 1; // 탐색 범위를 오른쪽으로 좁혀요
        }
    }
    
    printf("값 %d를 찾을 수 없습니다.\n", target);
    return 0;
}

 

 

 

🌟 과제 43, 선택 정렬을 이용한 내림차순 정렬

① 선택 정렬이란?

• 가장 큰 값을 찾아서 맨 앞으로 이동시키는 과정을 반복

 

② 내림차순 선택 정렬 동작 원리

• 배열에서 가장 큰 값 찾기
• 그 값을 맨 앞 위치와 교환
• 정렬된 부분을 제외하고 나머지 부분에서 다시 가장 큰 값을 찾기
• 모든 원소가 정렬될 때까지 반복

 

#include <stdio.h>

// 배열 출력 함수
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 2. 선택 정렬 - 내림차순
void selectionSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        int maxIndex = i;  // 최대값의 인덱스
        
        // 나머지 부분에서 최대값 찾기
        for (int j = i + 1; j < size; j++) {
            if (arr[j] > arr[maxIndex]) {
                maxIndex = j;
            }
        }
        
        // 교환
        int temp = arr[i];
        arr[i] = arr[maxIndex];
        arr[maxIndex] = temp;
    }
}

// 3. 삽입 정렬 - 오름차순
void insertionSort(int arr[], int size) {
    for (int i = 1; i < size; i++) {
        int key = arr[i];  // 삽입할 값
        int j = i - 1;
        
        // key보다 큰 값들을 오른쪽으로 이동
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        arr[j + 1] = key;  // key를 올바른 위치에 삽입
    }
}

 

 

 

🌟 과제 44, 삽입 정렬을 이용해서 정렬

① 삽입 정렬이란?

• 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어, 정렬되지 않은 부분은 원소를 하나씩 정렬된 부분의 적절한 위치에 삽입

 

② 삽입 정렬 동작 원리

• 첫 번째 원소는 이미 정렬된 것으로 간주
• 두 번째 원소부터 시작해서 정렬된 부분에서 자신의 위치 찾음
• 적절한 위치에 삽입하기 위해 필요한 원소들을 오른쪽으로 이동
• 모든 원소가 정렬될 때까지 반복

 

 

int main() {
    // 선택 정렬 테스트
    int arr1[] = {64, 34, 25, 12, 22, 11, 90};
    int size1 = 7;
    
    printf("=== 선택 정렬 (내림차순) ===\n");
    printf("정렬 전: ");
    printArray(arr1, size1);
    
    selectionSort(arr1, size1);
    
    printf("정렬 후: ");
    printArray(arr1, size1);
    
    printf("\n");
    
    // 삽입 정렬 테스트
    int arr2[] = {15, 11, 1, 3, 8};
    int size2 = 5;
    
    printf("=== 삽입 정렬 (오름차순) ===\n");
    printf("정렬 전: ");
    printArray(arr2, size2);
    
    insertionSort(arr2, size2);
    
    printf("정렬 후: ");
    printArray(arr2, size2);
    
    return 0;
}

 

 

 

 

 

 

 

 

 

미리보기용