c++) 정렬 알고리즘 종합 정리

안녕하세요 !!

오늘은 정렬 알고리즘들을 많이 모아 정리해놨습니다 ㅎㅎ

목적은 각 알고리즘들이 수행시간 실험을 하기 위해서였습니다.

구성은 다음과 같습니다.

○ 일반 

- 버블 정렬 (Bubble Sort)

○ 우선순위 큐 (Priority Queue)

- 선택 정렬 (Selection Sort)

- 삽입 정렬 (Insertion Sort)

- 힙 정렬 (Heap Sort)

○ 분할 통치 기법

- 합병 정렬 (Merge Sort)

- 퀵 정렬 (Quick Sort)

○ 기타 메소드

- checkTime() : 시간 측정 해줍니다

- swap() : 다들 아시죠?

- print() : 리스트를 출력합니다

시험들이 끝나고 심심해서 막 달렸네요 ㅋㅋ

작년 이맘때 열심히 공부했었는데, 오랜만에 작성하려고 하니 책도 뒤지고 나름 고생했습니다 ㅋㅋ

반나절이나 걸렸어요.. 

그러면 코드를 확인하겠습니다.

우선 정렬 알고리즘들이 있는 mySort.h입니다.

§ mySort.h

namespace 선언은 그냥 한번 해보고 싶었어요.. ㅋㅋ

#pragma once
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

namespace mySort {

	// 출력
	void print(vector<int> v) {
		for (int a : v) {
			cout << a << " ";
		}
		cout << endl << endl;
	}

	// swap
	void swap(int &a, int &b) {
		int tmp = a;
		a = b;
		b = tmp;
	}

	// time check
	void checkTime(void (*func)(vector<int>), vector<int> v) {
		clock_t start, end;
		double times;

		start = clock();
		func(v);
		end = clock();
		times = (double)(end - start) / (CLOCKS_PER_SEC);
		cout << "실행 시간 : " << times << " second" << endl << endl;
	}


	/*
	*	기본 버블  
	*/
	inline void bubble(vector<int> v) {
		for (int i = 0; i < v.size(); ++i) {
			for (int j = 0; j < v.size() - i - 1; ++j) {
				if (v[j] > v[j + 1]) swap(v[j], v[j + 1]);
			}
		}

	//	print(v);
	}

	/*
	* 우선순위 큐 정렬
	* 삽입 , 선택 , 힙 정렬
	*/
	// 삽입 정렬
	inline void insertion(vector<int> v) {
		vector<int>::iterator itr;
		int save;	// 이번 턴의 체크할 값

		for (itr = v.begin()+1; itr != v.end(); ++itr) {
			save = *itr;
			vector<int>::iterator itr2 = itr;

			// 기존의 체크한 값들을 비교
			// save 보다 크면 하나씩 뒤로 민다
			// => save가 들어갈 위치를 찾는 과정
			while (itr2 != v.begin() && *(itr2-1) > save) {
				*itr2 = *(itr2 - 1);
				--itr2;
			}
			*itr2 = save;
		}

	//	print(v);		
	}

	// 선택 정렬
	inline void selection(vector<int> v) {
		vector<int>::iterator minLoc;	// 가장 큰 값의 위치		
		vector<int>::iterator itr, itr2;
		int tmp;

		// 하나 남은 경우는 더 실행할 필요가 없다.
		for (itr = v.begin(); itr != v.end(); ++itr) {
			minLoc = itr;

			for (itr2 = itr + 1; itr2 != v.end(); ++itr2) {
				if (*itr2 < *minLoc) minLoc = itr2;
			}

			// swap
			swap(*itr, *minLoc);
		}

	//	print(v);
	}

	// 힙 정렬
	void downHeap(vector<int> &v, int i, int n) {
		int pos = 2 * i + 1;
		vector<int>::iterator left, right, down;

		// 범위 넘어가면 종료
		if (pos >= n) return;

		// 왼쪽, 오른쪽 노드 값 분배
		left = v.begin() + pos;
		right = v.begin() + pos + 1;

		// 내려갈 곳 찾음
		if (pos+1 < n) {
			if (*left < *right) down = right;
			else down = left;
		}
		else
			down = left;
		
		// 내가 내려갈 곳보다 작으면 안내려감
		if (v[i] >= *down) return;
		
		// 내려감
		swap(v[i], *down);
		// 재귀
		downHeap(v, (int)(down - v.begin()), n);		
	}

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

		for (int i = (n - 2) / 2; i >= 0; i--) {
			downHeap(v, i, n);
		}
	}

	inline void heap(vector<int> v) {
		int n = v.size();

		// phase 1 힙 생성
		buildHeap(v);

		// phase 2 힙 정렬
		while( n > 1 ) {
			swap(v[0], v[n-1]);
			--n;
			downHeap(v, 0, n-1);
		}
		
	//	print(v);
	}

	/*
	* 분할 통치법
	* 합병 정렬, 퀵 정렬
	*/
	// 합병 정렬
	void merging(vector<int> &v, int left, int size, int right) {
		vector<int> total;
		int i, j;

		i = left;	// L1 시작점
		j = size + 1;	// L2 시작점
		while (i <= size && j <= right) {
			if (v[i] > v[j]) {
				total.push_back(v[j++]);
			}
			else {
				total.push_back(v[i++]);
			}
		}

		// L2가 남은 경우
		if (i > size) {
			while (j <= right) {
				total.push_back(v[j++]);
			}
		}
		// L1이 남은 경우
		else {
			while (i <= size) {
				total.push_back(v[i++]);
			}
		}

		for (int x = left; x <= right; x++) {
			v[x] = total[x - left];
		}
	}

	void divide(vector<int> &v, int left, int right) {
		// 재귀 베이스
		if (left >= right) return;
		// 분할 포인트
		int size = (left + right) / 2;

		// 재귀
		divide(v, left, size);
		divide(v, size + 1, right);

		// 합병
		merging(v, left, size, right);

	}

	inline void merge(vector<int> v) {
		divide(v, 0, v.size() - 1);

	//	print(v);
	}

	// 퀵 정렬
	int partition(vector<int> &v, int left, int right, int pivot) {
		int i = left;
		int j = right - 1;

		// i가 j 넘기 전까지
		while (i <= j) {
			// 왼쪽은 피벗보다 작을때 i 이동
			// 오른쪽은 피벗보다 클 때 j 이동
			// 둘 다 성립하기 전까지 이동 후, 교환
			while (i <= j && v[i] <= pivot) ++i;
			while (j >= i && v[j] >= pivot) --j;
			if (i < j) swap(v[i], v[j]);
		}
		// 피벗과 작동이 멈춘 i 위치 교환
		// --> 피벗이 위치를 찾아 가는 것
		swap(v[i], v[right]);

		return i;
	}

	void quickSort(vector<int> &v, int left, int right) {
		int Pi;

		// 재귀 베이스
		if (left >= right) return;
		// 피벗 포인터 받기
		Pi = partition(v, left, right, v[right]);
		quickSort(v, left, Pi - 1);
		quickSort(v, Pi + 1, right);		
	}

	inline void quick(vector<int> v) {
		quickSort(v, 0, v.size()-1);

//		print(v);
	}
	
}	// namespace mySort

다음은 정렬을 실행시킬 main.cpp 입니다.

§ main.cpp

#include "mySort.h"

#define NUM		20000

using namespace mySort;

int main() {
	srand((unsigned int)time(nullptr));

	vector<int> sample;

	for (int i = 0; i < NUM; ++i) {
		int t = rand() % 100;
		sample.push_back(t);
	}

	std::cout << "<< Experiment start --- size : " << NUM << " >>" << endl;

	std::cout << "** bubble" << endl;
	checkTime(bubble, sample);

	std::cout << "** insertion" << endl;
	checkTime(insertion, sample);	

	std::cout << "** selection" << endl;
	checkTime(selection, sample);

	std::cout << "** heap" << endl;
	checkTime(heap, sample);

	std::cout << "** merge" << endl;
	checkTime(merge, sample);

	std::cout << "** quick" << endl;
	checkTime(quick, sample);

	return 0;
}

실험은 NUM 값만 변경해주면서 하시면 됩니다.

그럼 실험 결과를 보겠습니다.

First ) NUM = 1000

Second ) NUM = 10000

Third ) NUM = 20000

리스트의 크기가 커질수록 차이가 현격하게 증가하는 것을 볼 수 있습니다!

하지만 퀵 정렬은 짱짱..

§  분석 

우리가 알고 있는 알고리즘 수행 시간

알고리즘	수행 시간
버블 (Bubble)	O(n^2)
선택 (Selection)	O(n^2)
삽입 (Insertion)	O(n^2)
힙 (Heap)	O(n log n)
병합 (Merge)	O(n log n)
퀵 (Quick)	O(n log n)

O(n log n)의 성능을 가지는 알고리즘이 빠른건 다행이네요.

하지만 왜이렇게 급격하게 차이가 나는 걸까요?

n^2과 n log n의 크기의 차이가 그렇게 큰걸까요?

아래 그래프를 보면 그럴 수 있겠다는 생각이 듭니다 ㅋㅋ

< 그래프 정보 >

< 그래프 >

저 그래프들은 각 끝이 대략 100일 때 모습입니다.

이것들이 앞으로 얼마나 큰 차이가 날지는 뻔하죠?

이상으로 정렬 포스팅을 마치겠습니다.

다른 정렬들도 더 있지만, 가장 유명하고 기본적인 정렬들이에요!

다음에는 보다 좋은 자료로 찾아 오겠습니다!

요즘에 진로 준비에 바빠서.. ㅎㅎ ㅜㅜ

코드 자료 --> Git hub

( 그래프 참조 사이트 : https://www.desmos.com/calculator )

( 관련 정보 : https://ko.wikipedia.org/wiki/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EB%B6%84%EC%84%9D )