[알고리즘] C++ vector을 활용한 정렬 구현(버블, 삽입, 퀵)

 1. 이론

 

 알고리즘 중에 제일 대표적인 '정렬' 알고리즘이다. 알고리즘을 전부 공부한 것은 아니지만 아마 알고리즘을 공부할 때 가장 기초적으로 공부하는 알고리즘인 것 같다. (C언어를 공부할 때도 나왔으니......) 버블과 삽입은 어려운 알고리즘은 아니라고 생각했지만(이미 완성된 알고리즘을 구현하는 것 밖에 하지 않았지만......), 퀵의 구현을 공부할 때는 "대체 어떤 천재가 이런걸 만든거지?" 라는 생각이 들 정도로 감명받았다. 다음은 각각의 알고리즘의 이론이다.

 

- 버블

 

 버블알고리즘의 이름이 '버블'인 이유는 밑에서 부터 큰 숫자들이 마치 거품처럼 보글보글 올라오는 모습과 비슷하다고 하여 만들어진 이름이다. 최대값을 하나씩 가려내는 알고리즘이라고 생각하면 이해하기 쉬울 것이다. 다음과 같이 순서없이 정의된 데이터가 있다고 생각해보자

---

3 - 7 - 9 - 4 - 2

---

 처음부터 뒤로 가는 순서로 기준이 정해지며, 계산 대상은 기준인 숫자와 바로 뒤에 있는 숫자 두개이다. 기준 되는 숫자를 조금 특별하게 표지하면 다음과 같을 것이다.

 

---

3 - 7 - 9 - 4 - 2

---

 방법은 간단하다. 왼쪽과 오른쪽을 비교하여 왼쪽이 오른쪽 숫자보다 더 크다면 그 두 수의 위치를 바꾸면 되는 것이다. 지금의 두 숫자는 순서가 잘 되어 있으니, 다음 기준으로 넘어가면 된다. 다음 기준은 '7' 이고 계산대상은 기준과 그 다음 수인 '9'이다. 색갈로 표현하자면 다음과 같을 것이다.

---

3 - 7 - 9 - 4 - 2

---

 7과 9 또한 올바른 순서로 정렬되어 있으니, 넘어가면 된다. 그럼 기준은 9와 4가 되는데, 왼쪽의 숫자인 9가 4보다 크므로, 이 둘의 숫자를 바꾸면 다음과 같을 것이다.

---

3 - 7 - 4 - 9 - 2

---

 다음의 기준은 9와 2이다. 이 둘의 순서도 거꾸로이니 이 둘의 위치를 바꾸면 다음과 같을 것이다.

---

3 - 7 - 4 - 2 - 9

---

 이렇게 한번 위의 방법을 실행하면 최댓값이 올라온다. 이제 9는 제외하고 나머지 숫자인 3, 7, 4, 2를 대상으로 위의 방법과 같은 계산을 진행하면 남은 수중의 최댓값이 정해질 것이고 이 과정을 4번 반복하면 최종적으로 정렬된 수를 고를 수 있을 것이다.

 

 이렇게 최댓값이 한번의 순환마다 위로 올라오는 모습이 거품이 올라오는 것과 같아 버블정렬이라고 한다.(믿거나 말거나 ㅠㅠ) 다음은 삽입 정렬이다.

 

- 삽입

 

 삽입 정렬의 이름이 삽입인 이유는 말 그대로 숫자를 올바른 위치에 '삽입'하기 때문이다. 이번에도 똑같이 다음과 같이 무작위로 정렬된 데이터가 있다고 가정해보자.

---

3 - 7 - 9 - 4 - 2

---

 이번에도 순서는 버블과 같다. 왼쪽에서 오른쪽의 순서로 두개의 숫자가 계산의 대상이지만 조금은 다르다. 3, 7, 9는 이미 같은 순서이니 넘어가자. 대상은 9와 4이다. 똑같이 왼쪽이 작고 오른쪽이 크니 이 두 수를 교환해야겠지만, 버블정렬과는 다르게 작은 수인 '4'의 위치를 찾아서 넣어준다. 즉 3보다는 크고 7보다는 작으니 이 사이에 사를 넣어주고 4가 지나간 빈자리는 순서대로 채워주면 된다. 다음과 같은 수열이 될 것이다.

---

3 - 4 - 7 - 9 - 2

---

 그리고 대상은 다시 9와 2이다. 이번에도 오른쪽의 9보다 왼쪽의 2가 더 작으니 2의 자리를 찾아서 넣어주면 된다. 다음과 같은 그림이 될 것이다.

---

2 - 3 - 4 - 7 - 9

---

 이렇게 계산을 마치면 정렬된 수열을 볼 수 있다. 다음은 다음은 퀵 정렬이다.

 

- 퀵

 

 퀵 정렬은 기준을 잡고 그 기준되는 수보다 작은 수는 왼쪽 큰 수는 오른쪽으로 넘겨버리는 정렬이다. 똑같은 수열로 예시를 들겠다.

---

3 - 7 - 9 - 4 - 2

---

 위의 수 열에서 가장 첫번째인 3을 기준으로 잡아보자. 3을 기준으로 3보다 작은 수는 왼쪽에 3보다 큰수는 오른쪽으로 넘겨보겠다. 넘기는 숫자들의 순서는 중요하지 않으니, 다음과 같은 수열이 생성될 것이다.

---

4 - 2 - 3 - 7 - 9

---

 이제3을 기준으로 왼쪽과 오른쪽 수는 다른 수열이라고 생각하고 같은 방법을 적용한다. 즉 기준의 오른쪽에 해당하는 집합(7, 9)과 기준의 왼족에 해당하는 집합(4, 2)을 대상으로 위의 계산을 진행하면 된다. 오른쪽의 수열은 올바른 순서이니 왼쪽을 기준으로 진행해보자. 기준은 4이고 남아있는 2는 기준보다 작으니 왼쪽으로 넘긴다. 그럼 다음과 같이 정렬된 수열이 나타난다.

---

2 - 4 - 3 - 7 - 9

---

 퀵정렬은 가장 빠른 정렬법이어서 이름이 퀵이다. 시간 복잡도에 대한 내용도 넣고 싶었지만 너무 길어지기에 다음에 설명하겠다. 다음은 구현이다.

 

2. 구현

 

 모든 정렬은 클래스로 구현하였고 Sort라는 클래스를 상속받도록 하였다. C++에서 제공하는 vector를 사용하였다. 다음은 세개의 정렬방법을 구현한 헤더와 메소드 구현 코드이다.

 

- Sort.c

 

#pragma once
#include <vector>
#include <cstdio>

using namespace std;

class Sort
{
protected:
	vector<int>data;
public:
	Sort();
	~Sort();
	void defineArray();
	void printArray();
	void swap(int index1, int index2);
	int getSize() { return data.size(); }
};

 

- Sort.cpp

 

#include "Sort.h"



Sort::Sort()
{
}


Sort::~Sort()
{
}


void Sort::defineArray() {
	printf("데이터를 입력하세요! (종료: 0)\n");
	while (1) {
		int buff;
		scanf("%d", &buff);
		if (buff == 0)
			break;
		data.push_back(buff);
	}
}

void Sort::printArray() {
	for (int i = 0; i < data.size() - 1; i++)
		printf("%d -- ", data[i]);
	printf("%d\n", data[data.size() - 1]);
}

void Sort::swap(int index1, int index2) {
	int buff;
	buff			= data[index1];
	data[index1]	= data[index2];
	data[index2]	= buff;
}

 

- BubbleSort.h

 

#pragma once
#include "Sort.h"
class BubbleSort : public Sort
{
public:
	BubbleSort();
	~BubbleSort();
	void bubbleSort();
};

 

- BubbleSort.cpp

 

#include "BubbleSort.h"

BubbleSort::BubbleSort()
{
	defineArray();
}


BubbleSort::~BubbleSort()
{
}

void BubbleSort:: bubbleSort() {
	for (int i = data.size() - 1; i > 0; i--) {
		for (int j = 0; j < i; j++) {
			if (data[j] > data[j + 1])
				swap(j, j + 1);
		}
	}
}

 

- InsertSort.h

 

#pragma once
#include "Sort.h"
class InsertSort :
	public Sort
{
public:
	InsertSort();
	~InsertSort();
	void insertSort();
};

 

- InsertSort.cpp

 

#include "InsertSort.h"



InsertSort::InsertSort()
{
	defineArray();
}


InsertSort::~InsertSort()
{
}

void InsertSort::insertSort() {
	for (int i = 1; i < data.size(); i++) {
		if (data[i - 1] > data[i]) {
			for (int j = 0; j < i; j++) {
				if (data[j] > data[i]) {
					data.insert(data.begin() + j, data[i]);
					data.erase(data.begin() + i + 1);
					break;
				}
			}

		}
	}
}

 

- QuickSort.h

 

#pragma once
#include "Sort.h"
class QuickSort :
	public Sort
{
private:
	int standard;
public:
	QuickSort();
	~QuickSort();
	void quickSort(int Left, int Right);
	int partition(int Left, int Right);
};

 

- QuickSort.cpp

 

#include "QuickSort.h"



QuickSort::QuickSort()
{
	defineArray();
}


QuickSort::~QuickSort()
{
}

int QuickSort::partition(int Left, int Right) {
	int First = Left;
	int standard = data[First];
	Left++;

	while (Left <= Right) {
		while (data[Left] < standard && Left < Right)
			Left++;
		while (data[Right] > standard && Right >= Left)
			Right--;

		if (Left < Right)
			swap(Left, Right);
		else
			break;
	}
	swap(First, Right);
	return Right;
}

void QuickSort::quickSort(int Left, int Right) {
	if (Left < Right) {
		int standard = partition(Left, Right);
		quickSort(Left, standard - 1);
		quickSort(standard + 1, Right);
	}
}

 

 - main() 함수

 

 다음은 main()함수이다. 정렬을 전부 사용할 수 있도록 코드를 작성해보았다.

 

#include "BubbleSort.h"
#include "InsertSort.h"
#include "QuickSort.h"

int main(void) {
	while (1) {
		printf("[Bubble: 1, Insert: 2, Quick: 3 Exit: 4 ]");
		int input;
		scanf("%d", &input);

		switch (input) {
		case(1): {
			BubbleSort bSort;
			bSort.bubbleSort();
			printf("[BubbleSort]\n");
			bSort.printArray();
			break;
		}
		case(2): {
			InsertSort iSort;
			iSort.insertSort();
			printf("[InsertSort]\n");
			iSort.printArray();
			break;
		}
		case(3): {
			QuickSort qSort;
			qSort.quickSort(0, qSort.getSize() - 1);
			printf("[InsertSort]\n");
			qSort.printArray();
			break;
		}
		default: return 0;
		}
	}
}

 

 

3. 결어

 

 첫 알고리즘에 대한 구현법과 이론 설명이어서 부족한 점이 많은 것 같았다. 앞으로 이 카테고리에 많은 알고리즘을 설명하는 글을 올렸으면 좋겠다.