[정렬 알고리즘] 선택, 삽입, 버블 알고리즘(Selection, Insertion, Bubble sort algorithm)

1. 선택정렬

정렬이라고 하면 가장 먼저 떠오르는 방식의 알고리즘이다. 오름차순을 기준으로 첫 요소부터 끝까지 차례대로 탐색하여 가장 작은 것을 골라 제일 앞의 요소와 자리를 바꾸고 정렬된 첫번째 요소의 다음 번째인 두번째 요소부터 다시 차례대로 탐색하여 가장 작은 숫자와 자리를 바꾸는 것을 반복하여 정렬하는 알고리즘이다. 시간복잡도는 O(N^2).

 

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

//벡터 요소를 서로 바꾸는 함수
void Swap(int& a, int& b)
{
    int temp;

    temp = a;
    a = b;
    b = temp;
}

void SelectionSort(vector<int> &num)
{
	//요소의 처음부터 끝까지
    for (int i = 0; i < num.size(); i++)
    {
        int min = 10000;
        int minIdx = 0;
        //정렬되지 않은 요소부터 끝까지
        for (int j = i; j < num.size(); j++)
        {
        	//가장 작은 요소를 찾아서 인덱스를 기억
            if (num[j] < min)
            {
                min = num[j];
                minIdx = j;
            }
        }
        //정렬해야하는 위치의 요소와 가장 작은 요소의 위치를 바꿈
        Swap(num[i], num[minIdx]);
    }
}

int main()
{
    vector<int> v_num;

    v_num.push_back(1);
    v_num.push_back(7);
    v_num.push_back(3);
    v_num.push_back(6);
    v_num.push_back(9);
    v_num.push_back(8);
    v_num.push_back(2);
    v_num.push_back(5);
    v_num.push_back(4);

    SelectionSort(v_num);

    for (int i = 0; i < v_num.size(); i++)
    {
        cout << v_num[i] << " ";
    }
    return 0;
}

 

2. 삽입정렬

손에 가지고 있는 카드를 정렬하는 것과 비슷하다. 앞에서 정렬된 숫자들과 비교하여 올바른 위치에 삽입하여 정렬하는 알고리즘으로 두번째 요소부터 시작해 앞의 요소들과 비교하여 삽입될 위치를 찾고 해당 요소를 삽입하기 위해 거쳐온 요소들을 한칸씩 뒤로 옮긴다. 시간복잡도는 O(N^2).

 

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

//삽입정렬
void InsertionSort(vector<int>& num)
{
	//요소의 두번째부터 끝까지
    for (int i = 1; i < num.size(); i++)
    {
    	//정렬해야할 요소
        int cur = num[i];
        int j;
		//역순으로 위치를 찾을때까지
        for (j = i-1; j >= 0 && cur < num[j]; j--)
        {
        	//요소를 한칸씩 옮기기
            num[j + 1] = num[j];
        }
		//해당 위치에 정렬해야할 요소 삽입
        num[j + 1] = cur;
    }
}

int main()
{
    vector<int> v_num;

    v_num.push_back(1);
    v_num.push_back(7);
    v_num.push_back(3);
    v_num.push_back(6);
    v_num.push_back(9);
    v_num.push_back(8);
    v_num.push_back(2);
    v_num.push_back(5);
    v_num.push_back(4);

    InsertionSort(v_num);

    for (int i = 0; i < v_num.size(); i++)
    {
        cout << v_num[i] << " ";
    }
    return 0;
}

 

3. 버블정렬

거품이 올라가듯이 요소의 처음부터 끝까지 바로 앞의 요소만을 비교하는 것을 반복하여 위치를 바꾸면서 정렬되는 알고리즘이다. 여러번의 회전으로 정렬이 완료된다. 시간복잡도는 O(N^2)

 

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

void Swap(int& a, int& b)
{
    int temp;

    temp = a;
    a = b;
    b = temp;
}

//버블 정렬
void BubbleSort(vector<int>& num)
{
	//정렬되지 않은 요소 끝까지(끝에서부터 정렬 됨)
    for (int j = num.size() - 1; j >= 0; j--)
    {
    	//처음부터 차례로 비교하여 스왑
        for (int i = 0; i < j; i++)
        {
            if (num[i] > num[i + 1])
                Swap(num[i], num[i + 1]);
        }
    }
}

int main()
{
    vector<int> v_num;

    v_num.push_back(1);
    v_num.push_back(7);
    v_num.push_back(3);
    v_num.push_back(6);
    v_num.push_back(9);
    v_num.push_back(8);
    v_num.push_back(2);
    v_num.push_back(5);
    v_num.push_back(4);

    BubbleSort(v_num);

    for (int i = 0; i < v_num.size(); i++)
    {
        cout << v_num[i] << " ";
    }
    return 0;
}