묻공러
[C++ 자/알 Note] 정렬 - 버블, 선택, 삽입
묻공러
묻지마공부
묻공러
전체
오늘
어제
  • 분류 전체보기 (521) N
    • C (54)
      • [코드조선] C 핵심 (35)
      • [언어본색] C 기초 (19)
    • C++ (72)
      • [루키스] C++ (9)
      • [루키스] 콜백함수 (6)
      • [루키스] STL (8)
      • [루키스] Modern C++ (11)
      • [노코프] C++ (10)
      • [노코프] Tips (16)
      • [일지] C++ (12)
    • C# (20) N
      • [루키스] C# (9)
      • [루키스] 자료구조 (3)
      • [루키스] 실전 문법 (8) N
    • 자료구조 & 알고리즘 (50)
      • [코드조선] C 자료구조 & 알고리즘 (6)
      • [합격자되기] C++ 코딩테스트 (12)
      • [루키스] C++ 자료구조 & 알고리즘 (32)
    • CS (69)
      • [널널한 개발자] CS 개론 (19)
      • [혼자 공부하는] 컴퓨터 구조 (16)
      • [혼자 공부하는] 운영체제 (18)
      • [널널한 개발자] 네트워크 (16)
    • 게임 그래픽스 (46)
      • [전북대] OpenGL (25)
      • [일지] DirectX (21)
    • 게임 엔진 - 언리얼 (123)
      • [코드조선] 언리얼 (53)
      • [코드조선] 언리얼 데디서버 (8)
      • [일지] 언리얼 (59)
      • [일지] 언리얼 (2) (3)
    • 게임 엔진 - 유니티 (14) N
      • [최적화] 유니티 (4)
      • [루키스] 유니티 (10) N
    • 게임 서버 (17)
    • 게임 수학 & 물리 (19)
      • 게임 수학 (12)
      • 게임 물리 (7)
    • GIT & GITHUB (4)
    • 영어 (18)
      • [The Outfit] 대본 공부 (11)
      • the others (7)
    • 그 외 (14)
      • In (5)
      • Out (5)
      • Review (4)

인기 글

최근 글

hELLO · Designed By 정상우.
자료구조 & 알고리즘/[루키스] C++ 자료구조 & 알고리즘

[C++ 자/알 Note] 정렬 - 버블, 선택, 삽입

2025. 1. 19. 12:20

버블정렬

버블정렬의 핵심은 순서대로 앞뒤로 비교해 가며

정렬을 진행을 하는 것이다

 

버블정렬 예시

 

버블정렬 구현

void BubbleSort(vector<int>& v)
{
	const int n = (int)v.size();

	// (N-1) + (N-2) + ... + 2 + 1
	// 등차수열의 합 = N * (N-1) / 2
	// O(N^2)
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < (n - 1 - i); j++)
		{
			if (v[j] > v[j + 1])
			{
				int temp = v[j];
				v[j] = v[j + 1];
				v[j + 1] = temp;
			}
		}
	}
}

 


 

선택정렬

선택정렬의 핵심은 순회하면서 가장 최소값을 찾아내서

정렬을 진행하는 것이다

 

선택정렬 예시

선택정렬 구현

void SelectionSort(vector<int>& v)
{
	const int n = (int)v.size();

	// O(N^2)
	for (int i = 0; i < n - 1; i++)
	{
		int bestIdx = i;

		for (int j = i + 1; j < n; j++)
		{
			if (v[j] < v[bestIdx])
				bestIdx = j;
		}

		// 교환
		int temp = v[i];
		v[i] = v[bestIdx];
		v[bestIdx] = temp;
	}
}

 


 

삽입정렬

삽입정렬의 핵심은 값을 하나씩 추가해 가며

본인이 들어갈 위치에 들어가는 것이다

 

삽입정렬 예시

 

삽입정렬 구현

void InsertionSort(vector<int>& v)
{
	const int n = (int)v.size();

	// O(N^2)
	for (int i = 1; i < n; i++)
	{
		int insertData = v[i];

		int j;
		for (j = i - 1; j >= 0; j--)
		{
			if (v[j] > insertData)
				v[j + 1] = v[j];
			else
				break;
		}

		v[j + 1] = insertData;
	}
}

 


정렬 시/공간복잡도

버블, 선택, 삽입은 모두 시간복잡도는 평균 O(N^2)이고

공간복잡도는 O(1)이다

저작자표시 비영리 변경금지 (새창열림)

'자료구조 & 알고리즘 > [루키스] C++ 자료구조 & 알고리즘' 카테고리의 다른 글

[C++ 자/알 Note] 해시테이블  (1) 2025.01.19
[C++ 자/알 Note] 정렬 - 힙, 병합, 퀵  (0) 2025.01.19
[C++ 자/알 Note] 레드블랙트리 - 삭제  (0) 2025.01.19
[C++ 자/알 Note] 레드블랙트리 - 개념 및 삽입  (0) 2025.01.19
[C++ 자/알 Note] 이진탐색트리  (0) 2025.01.19
'자료구조 & 알고리즘/[루키스] C++ 자료구조 & 알고리즘' 카테고리의 다른 글
  • [C++ 자/알 Note] 해시테이블
  • [C++ 자/알 Note] 정렬 - 힙, 병합, 퀵
  • [C++ 자/알 Note] 레드블랙트리 - 삭제
  • [C++ 자/알 Note] 레드블랙트리 - 개념 및 삽입
묻공러
묻공러
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.