버블, 선택, 삽입 정렬 + 퀵 정렬

gbleem 2025. 2. 25. 11:52

업데이트) 병합 정렬과 이분탐색 알고리즘 추가

자세한 예시는 해당 글에 있고, 전반적인 정리는 아래 링크의 글을 참고하면 된다.

https://gbleem.tistory.com/128

정렬 및 탐색 알고리즘 정리

1. 정렬 알고리즘1 - 1. 버블정렬배열에서 두개의 원소 선택하고 비교 후, 왼쪽 원소가 오른쪽 원소보다 큰 경우 swap 한다.시간 복잡도는 O(N^2), 공간 복잡도는 O(1)만약 아래 코드에서 swap이 발생하

gbleem.tistory.com

1. 버블 정렬

개념

앞에서부터 시작해서 자기 자신과 하나 뒤에 값을 비교하는데, 자신보다 작은 값이 나온 순간 swap을 해주는 과정을 통해 정렬한다.
한바퀴 순환을 하고나면, 맨 뒤의 값이 가장 큰 값이 된다.
N개의 데이터가 있을 때, 이중 for문을 모두 순환해야 하므로 O(N^2)의 시간 복잡도를 가진다.

예시

4 6 2 9 1 이라는 값이 있다고 할 때
첫번째 순환에 있어서는 4 6 2 9 1 -> 4 2 6 9 1 -> 4 2 6 1 9 으로 바뀌고
두번째 순환에서는 4 2 6 1 9 -> 2 4 6 1 9 -> 2 4 1 6 9 로 바뀐다.
세번째 순환에서는 2 4 1 6 9 -> 2 1 4 6 9
마지막 순환에서 2 1 4 6 9 -> 1 2 4 6 9 로 정렬이 완료된다.

코드

//Bubble Sort

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> vec = { 4,6,2,9,1 };

	for (int i = 0; i < vec.size(); ++i)
	{
		for (int j = 0; j < vec.size() - i - 1; ++j)
		{
			if (vec[j] > vec[j + 1])
				swap(vec[j], vec[j + 1]);
		}
	}
	for (const auto v : vec)
		cout << v << " ";
}

2. 선택 정렬

개념

앞에서부터 시작해서, 자신의 자리의 값과 나머지 값들을 모두 비교해서, 가장 작은 값을 자신과 swap 하는 과정을 통해 정렬한다.
한바퀴 순환을 하고나면, 맨 앞의 값이 가장 작은 값이 된다.
시간 복잡도는 O(N^2)이다.

예시

4 6 2 9 1 이라는 값이 있을 때
첫번째 순환으로 1 6 2 9 4
두번째 순환으로 1 2 6 9 4
세번째 순환으로 1 2 4 9 6
네번째 순환으로 1 2 4 6 9 정렬 완료

코드

//selection sort

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> vec = { 4,6,2,9,1 };

	for (int i = 0; i < vec.size() - 1; ++i)
	{
		int idx = i;
		for (int j = i + 1; j < vec.size(); ++j)
		{
			if (vec[j] < vec[idx])
				idx = j;
		}
		
		swap(vec[i], vec[idx]);			
	}
	for (auto v : vec)
		cout << v << " ";	
}

3. 삽입 정렬

개념

앞에서부터 시작하는데 (해당 인덱스를 i라고 하면) 다음 값(i + 1)과 비교해서 만약 i+1의 값이
- 더 작은 경우 0 ~ i 까지의 값과 모두 비교하면서 i+1에 해당하는 값보다 작은 값 뒤로 위치시켜주면서 정렬하는 방식이다.
- 더 큰 경우 i를 하나 증가시켜 반복한다.
삽입 정렬은 O(N^2)의 시간 복잡도 이지만, 최선의 경우(정렬된 경우) O(N)의 복잡도가 된다.

예시

4 6 2 9 1이 있을때
4를 6과 비교, 6이 4 보다 크기 때문에 i 증가
- 4 6 2 9 1
6과 2를 비교
- 2가 6보다 작으므로 swap
- 2가 4보다 작으므로 swap
- 2 4 6 9 1
9와 6을 비교 (2는 맨앞으로 이동)
- 9가 6 보다 크므로 i 증가
1과 9를 비교
- 1은 모든 숫자보다 작으므로
- 계속 swap해서 맨 앞으로 이동
- 1 2 4 6 9 정렬 완료

코드

//insertion sort
#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> vec = { 4,6,2,9,1 };

	int value, j;
	for (int i = 1; i < vec.size(); i++) 
	{ 
		value = vec[i];
		for (j = i - 1; j >= 0; j--) 
		{
			if (vec[j] > value)
				swap(vec[j + 1], vec[j]);
			else
				break;
		}
	}
	for (auto v : vec)
		cout << v << " ";
}

4. 퀵 정렬

개념

피벗이라는 기준점을 기반으로 피벗의 왼쪽은 작은값을 오른쪽은 큰 값으로 나눠서 정렬하는 방식
정렬하고자하는 배열을 나눠서 각자 나눠진 배열을 정렬하여 전체 배열을 정렬하게 된다.
최적(평균)의 경우 O(NlogN) 이지만 최악의 경우 O(N^2)

예시

4 6 2 9 1이 있다고 할때, low는 0 high는 4이다
첫번째 Partition 함수를 실행하게 되면,
- mid = 2(인덱스), swap을 통해 중앙값을 맨 뒤로 보내면 4 6 1 9 2 가 된다.
- pivot은 2(값) 이고 idx는 -1부터 시작하게 된다.
- for문
  - 4와 6은 2(피벗)보다 크므로 아무 동작 x
  - 1은 2보다 작으므로 idx++ 한 후 swap -> 1 6 4 9 2
  - 9는 마찬가지로 2보다 크므로 아무동작 안하고 for문 종료
  - 2라는 피벗값 (인덱스는 high)을 2보다 작은 값들이 있는(0 ~ idx) 위치의 다음 위치와 swap하기 -> 1 2 4 9 6
- 이후 1이라는 피벗 위치를 return
Partition함수가 끝나고 pos는 1이 된다.
이후 QuickSort 재귀함수 호출을 통해
- QuickSort(vec, 0, 0)과 QuickSort(vec, 2, 4)를 실행하게 될 것인데
- QuickSort(vec, 0, 0)의 경우 low < high 를 만족하지 않기에 종료 (정렬되었다는 뜻)
- QuickSort(vec, 2, 4)만 실행하면 된다.
두번째 Partition 함수는
- mid = 3, swap을 통해 1 2 4 6 9 가 된다.
- pivot은 9이고 idx 는 1에서 시작
- for문
  - 4(i = 2)는 9(피벗)보다 작으므로 idx++ (idx = 2)하고 swap -> 1 2 4 6 9 그대로
  - 6(i = 3)도 9보다 작으므로 idx++ (idx = 3) 하고 swap -> 1 2 4 6 9 그대로고 for문 종료
- idx는 3인데 idx+1하고 high값과 swap한 후(그대로) idx + 1값인 4를 return
이후 QuickSort(vec, 2, 4) 을 한번 실행하고 Partition(vec, 2, 3)을 통해 2를 return
이후 QuickSort가 low < high 조건을 만족하는 경우가 없어 종료된다.

코드

// quick sort

#include <iostream>
#include <vector>
using namespace std;

int Partition(vector<int>& vec, int low, int high)
{
	//중간값 찾기
	int mid = (low + high) / 2;

	//중간값을 맨 값이랑 swap
	swap(vec[mid], vec[high]);

	//중간값을 pivot으로 설정
	int pivot = vec[high];

	//시작 인덱스 설정
	int idx = low - 1;

	for (int i = low; i < high; ++i)
	{
		//피벗보다 작은 값을 왼쪽으로 몰아버리기
		if (vec[i] < pivot)
		{
			idx++;
			swap(vec[i], vec[idx]);
		}
	}
	//피벗을 정렬한 값 중앙으로 옮겨주기
	swap(vec[idx + 1], vec[high]);

	//정렬한 vec의 피벗 위치 return
	return idx + 1;
}

void QuickSort(vector<int>& vec, int low, int high)
{
	if (low < high)
	{
		//피벗보다 작은 값을 왼쪽 큰 값을 오른쪽으로 바꿔주기
		int pos = Partition(vec, low, high);

		//피벗을 기준으로 재귀함수 시작
		QuickSort(vec, low, pos - 1);
		QuickSort(vec, pos + 1, high);
	}
}


int main()
{
	vector<int> vec = { 4, 6, 2, 9, 1 };

	int low = 0;
	int high = vec.size() - 1;

	QuickSort(vec, low, high);

	for (auto v : vec)
		cout << v << " ";
}