동적 배열로 삽입 정렬 마스터하기 - C++ 튜토리얼

소개

이 랩에서는 C++ 에서 동적 배열을 사용하여 삽입 정렬 (Insertion Sort) 알고리즘을 구현하는 방법을 배웁니다. 이 알고리즘은 리스트를 정렬된 부분과 정렬되지 않은 부분으로 나누어 작동하는 간단한 정렬 알고리즘으로, 정렬되지 않은 리스트의 각 요소를 정렬된 리스트의 올바른 위치에 삽입합니다.

동적 배열 생성

먼저, 사용자가 결정한 크기로 정수형 동적 배열을 생성하고, 1 에서 100 사이의 임의의 정수로 채워야 합니다.

#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
    int *arr;
    int size, i;

    cout << "Enter the size of the array: ";
    cin >> size;

    // create dynamic array
    arr = new int[size];

    // fill array with random integers between 1 and 100
    for(i=0; i<size; i++) {
        arr[i] = rand() % 100 + 1;
    }

정렬되지 않은 배열 출력

다음으로, 정렬되지 않은 배열의 내용을 사용자에게 표시합니다.

    // display unsorted array
    cout << "Unsorted array: ";
    for(i=0; i<size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

삽입 정렬 알고리즘 구현

이제 배열을 오름차순으로 정렬하는 삽입 정렬 알고리즘을 구현합니다.

    // insertion sort
    int j, temp;
    for(i=1; i<size; i++) {
        temp = arr[i];
        j = i - 1;
        while(j>=0 && arr[j]>temp) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = temp;
    }

정렬된 배열 출력

이제 정렬된 배열의 내용을 사용자에게 표시합니다.

    // display sorted array
    cout << "Sorted array: ";
    for(i=0; i<size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

메모리 해제

마지막으로, 동적 배열이 사용한 메모리를 해제합니다.

    // free memory
    delete [] arr;

    return 0;
}

프로그램 컴파일 및 실행

파일을 ~/project 디렉토리에 "sort.cpp"로 저장합니다.

터미널에서 프로그램을 컴파일하고 실행합니다:

cd ~/project
g++ sort.cpp -o sort
./sort

요약

이번 랩에서는 C++ 에서 동적 배열을 사용하여 삽입 정렬 (Insertion Sort) 알고리즘을 구현하는 방법을 배웠습니다. 사용자가 결정한 크기로 동적 배열을 생성하고, 임의의 정수로 채운 다음, 삽입 정렬 알고리즘을 구현하고, 마지막으로 정렬된 배열을 사용자에게 표시했습니다. 또한 동적 배열이 사용한 메모리를 해제하는 방법도 배웠습니다.

동적 배열을 사용한 삽입 정렬

소개