[C++] 정렬(sort) 알고리즘

username_oy·2024년 6월 5일

자료구조 & 알고리즘

목록 보기

1/1

자료구조 공부 시, 정렬을 제일 먼저 공부하는 이유?

정렬 알고리즘을 공부하는 것은 단순히 데이터를 정렬하는 방법을 배우는 것 이상의 의미가 있습니다.
다양한 알고리즘들의 특징을 이해하고, 어떤 상황에서 어떤 알고리즘이 가장 효율적인지 판단할 수 있는 능력이 중요합니다.
예를 들어 Big O 는 알고리즘의 효율성을 나타내는 지표인데, 이는 입력값의 크기에 따라 알고리즘이 얼마나 많은 시간이 걸리는지를 나타냅니다.
예를 들어 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort), 버블 정렬(Bubble Sort) 의 경우 시간 복잡도는 O(n^2) 입니다.
이는 입력 데이터의 크기가 n일 때, 최대 n^2 만큼의 시간이 소요됨을 의미합니다.
이들은 구현이 쉬워서 작은 데이터 집합에는 적합하지만, 큰 데이터에는 비효율적이다.
큰 데이터에 더 효율적인 알고리즘을 사용하고자 한다면, 병합 정렬이나 퀵 정렬 과 같은 것을 사용한다면 이는 O(n log n)의 시간 복잡도를 가지는데, 이는 동일한 크기를 입력하는데 있어 훨씬 더 빠른 속도로 실행될 수 있다는 것을 의미합니다.

교환(swap)

교환(swap)은 두 변수의 값을 교환하는 연산입니다.

라이브러리 함수인 std::swap을 사용

#include <algorithm>
int main() {
	int a = 10, b = 20;
    std::swap(a, b);
}

algorithm 헤더를 사용하여 swap 함수를 사용할 수 있습니다.
만약 헤더를 사용하지 못하는 상황일 경우, 값을 잠시 내려놓을(임시로 저장) 변수를 만들어 a와 b의 값을 교환합니다.

int main() {
	int a = 10, b = 20;
    int temp;
    
    temp = a;
    a = b;
    b = temp;
}

swap은 정렬에서 순서를 변경하여 데이터를 정렬할 때 필요합니다.
예를 들어, 배열의 두 요소를 교환해야할 때 주로 swap 연산이 사용됩니다.

선택 정렬(Selection Sort)

정렬 맨 앞에서 부터 정렬을 완성해 나가는 정렬 방식입니다.
배열에서 최솟값을 찾아 맨 앞부터 둔다.
일반적으로 데이터의 교환이 이동 작업보다 복잡하다.

void selectionSort(int* arr, int size) {
	int i, j, minIdx, temp;
    
    for (i = 0; i = size - 1; i++) // 정렬기준
    	{
        minIdx = i;
        for(j = i + 1; j < size; j++) // 비교
        	{
            if (arr[j] < arr[minIdx]) // 비교 값이 최소값보다 작다면
            	{
                minIdx = j;
                }
            }
            swap(int

삽입 정렬(insertion sort)

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 정렬
삽입을 위해 선택한 값을 임시변수에 저장한다.
내부 반복문은 삽입 위치를 찾을 때까지 임시 변수의 값과 비교한다.

void insertion(int* pArr, int size)
{
	int i, j, temp;

	for (i = 1; i < size; i++) // 인덱스 [1]번째부터 배열 끝까지 반복
	{
		temp = pArr[i]; // temp 변수 초기화
		for (j = i; j > 0 && (pArr[j-1] > temp); j--) // 정렬하고자 하는 index가 i이기 때문에 j = i, j가 0보다 크고, 임시변수에 넣은 인덱스가 j - 1보다 작을 때
		{
			pArr[j] = pArr[j - 1]; // 그 전값을 뒤로 미룬다.
		}
		pArr[j] = temp;
	}
}

버블 정렬(bubble sort)

서로 인접한 2개의 요소를 비교, 정렬하는 알고리즘
일반적으로 데이터의 교환이 이동 작업보다는 복잡하다.
공간 복잡도 : O(1) -> 한 개의 임시 변수가 필요하다.

void bubble(int* pArr, int size)
{
	int i, j;

	for (i = 0; i < size - 1; i++) //패스 횟수
	{
		for (j = 0; j < size - 1 - i; j++) //비교 횟수
		{
			if (pArr[j] > pArr[j + 1])
			{
				swap(int, pArr[j], pArr[j + 1]);
			}
		}
	}
}

username_oy