정렬 - 추가중

	Best	Worst	Memory
선택정렬	n^2	n^2	1
버블정렬	n	n^2	1
삽입정렬	n	n^2	1
합병정렬	n log n	n log n	n
힙정렬		n log n	1
퀵정렬	n log n	n log n	1

 

아래 설명은 정렬할 데이터를 vector<int>로 가정하고 설명한다.

 

1. 선택정렬

처음부터 끝까지 순회하며 현재 위치에 들어갈 값을 찾아 넣는 방식

void sort(vector<int>& v)
{
    for (int i = 0; i < v.size(); i++)
    {
        int min_index = i;

        for (int j = i + 1; j < v.size(); j++)
        {
            if (v[min_index] > v[j]) {
                min_index = j;
            }
        }

        int temp = v[i];
        v[i] = v[min_index];
        v[min_index] = temp;
    }
}

 

 

2. 버블정렬

인접한 두 수를 비교하여 작은 값을 앞으로, 큰 값을 뒤로 보내주며 정렬하는 방식

(가장 비 효율적인 방법)

void sort(vector<int>& v)
{
    for (int i = 0; i < v.size(); i++)
    {
        for (int j = i + 1; j < v.size(); j++)
        {
            if (v[i] > v[j])
            {
                int temp = v[i];
                v[i] = v[j];
                v[j] = temp;
            }
        }
    }
}

 

 

3. 삽입 정렬

선택된 값이 들어갈 위치를 찾아 해당 위치에 넣어주며 정렬하는 방식

 

 

이후 추가 예정