[알고리즘] In-place정렬

치치·2025년 1월 14일

알고리즘

알고리즘C++

목록 보기

2/24

거품정렬, 선택정렬, 삽입정렬에 대해 알아보겠다
세가지의 정렬을 알아보기전에 In-place정렬이 무엇인지 알아보자

In-Place정렬

쉽게 말하자면 외부 메모리를 거의 쓰지않고 주어진 배열 내부의 swap이나 대입으로 작업을 수행하는 것
제자리 알고리즘 이라고도 한다

버블정렬 : swap

선택정렬 : swap

삽입정렬 : 대입

버블 정렬

서로 인접한 두 원소를 비교하여 정렬하는 알고리즘이다

정렬이 다 되고 출력해보면 오름차순으로 정렬이 된다

버블정렬의 시간복잡도 O(N²)

#include <iostream>
#define SIZE 5
using namespace std;

int main()
{
#pragma region 거품 정렬
	// 오름차순 정렬

	int array[SIZE] = { 5, 8, 2, 1, 4 };
    
	// 회차
	for (int i = 0; i < SIZE - 1; i++)
	{
		// 안쪽 정렬
		for (int j = 0; j < (SIZE - i) - 1; j++)
		{
			// 왼쪽이 더 크다면 swap
			if (array[j] > array[j + 1])
			{
				swap(array[j], array[j + 1]);
			}
		}
	}

	for (const int& element : array)
	{
		cout << element << " ";
	}

#pragma endregion

	return 0;
}

바깥쪽for문은 안쪽을 비교하는 과정을 한번 행하는 회차를 의미한다
-> SIZE - 1회차에서 정렬이 완료되고 마지막 맨 앞 자료형은 알아서 정렬되기 때문에 SIZE만큼 반복 할 필요가 없다
안쪽 for문은 인접한 요소간 비교하고 swap하기 위한 반복문이다
-> j값이 (SIZE - i) -1까지만 반복하는 이유는
한번 회차를 진행하고 나면 맨 마지막 자료형의 갑은 정렬이 완료된 상태이기 때문에 비교 연산 할 필요가 없다
-> 그래서 - i를 해주는 것

선택 정렬

주어진 리스트 중에 최소값을 찾아서 맨 앞에 위치한 결과를 교체하는 방식으로 정렬하는 알고리즘이다

선택정렬의 시간복잡도 O(N²)

주어진 배열이나 리스트 요소 중에서 최소값을 찾는다
최소값을 맨 앞에 위치한 값과 교체한다
맨 처음 위치를 제외한 나머지 리스트를 같은 방법으로 교체한다

값을 교체할때는 swap을 사용하여 추가적인 메모리를 사용하지 않는다

#include <iostream>
#define SIZE 5
using namespace std;

int main()
{
#pragma region 선택 정렬

	int min = 0;
	int minIndex = 0;

	int array[SIZE] = { 6, 2, 8, 1, 0 };

	// 마지막 값은 알아서 정렬되기 때문에 SIZE - 1
	// SIZE로 해도 무관하긴 함
	// 0 1 2 3 
	for (int i = 0; i < SIZE - 1; i++)
	{
		// 1. 최소값 찾기
		min = array[i];
		minIndex = i;

		for (int j = i + 1; j < SIZE; j++)
		{
			// 최소값 교체
			if (array[j] < min)
			{
				min = array[j];
				minIndex = j;
			}
		}
		// 실제 값 변경
		swap(array[i], array[minIndex]);
	}

	for (const int& element : array)
	{
		cout << element << " ";
	}
#pragma endregion
	return 0;
}

바깥쪽 for문은 최소값을 하나씩 대입해주는 것
안쪽 for문은 현재 위치인 i값의 다음 요소들과 값을 비교하여 최소값을 갱신시켜주는 것

삽입 정렬

데이터를 하나씩 확인하면서 이미 정렬된 부분과 비교하여 자신의 위치를 찾아 삽입하는 방식으로 정렬하는 알고리즘이다

삽입정렬의 시간복잡도 O(N²)

key값은 내가 삽입하고 싶은 값이다
-> 첫 번째 원소[0]는 이미 정렬된 상태로 간주되기 때문에 key값을 저장하는 반복은 [1]부터 SIZE까지
안쪽 for문의 조건식은 j값이 i - 1부터 시작해서 j--를 거쳐 j가 0과 같거나 작아지면 중지한다
그리고 array [j] 값이 key값보다 크다면 반복, array [j]값이 더 작아지면 중지
-> i의 앞쪽에 정렬된 값을 뒤에서 부터 차례로 확인하는 것
key값보다 array [j] 값보다 작다면, array[j+1]의 위치에 array[j]값을 대입
-> 기존의 key값은 변수에 저장되어 있기 때문에 덮어씌워져도 괜찮음 (나중에 key값을 다시 대입할 예정)
안쪽 for문이 종료되면 비교 위치에 key값을 다시 삽입한다

#include <iostream>
#define SIZE 5
using namespace std;

int main()
{
#pragma region 삽입 정렬
	// 키값과 왼쪽에 값들을 비교한 뒤 그 자리에 키값을 대입

	// 0번째 인덱스의 수는 그 자체로 정렬이 되어있으므로 [1]부터 시작
	int array[SIZE] = { 6,12,4,1,7 };

	int key = 0;

	int j = 0;

	// 1 2 3 4 
	for (int i = 1; i < SIZE; i++)
	{
		// 키값 저장
		key = array[i];

		for (j = i - 1; j >= 0 && array[j] > key; j--)
		{
			// key위치의 인덱스의 값을 j값으로 대입
			array[j + 1] = array[j];
		}		
		// 비교 위치에 key값 삽입 (j가 -가 되는걸 방지)
		array[j + 1] = key;
	}
	
	for (const int& element : array)
	{
		cout << element << " ";
	}
#pragma endregion

	return 0;
}