5-1. 버블 정렬, 선택 정렬, 삽입 정렬

상대적으로 비효율적으로 동작하는 기본 정렬들이다.

 

1. 버블 정렬(Bubble Sort)

바로 옆의 원소와 비교하며 큰 수를 마지막에 오게 한다.

루프 한 번마다 큰 수를 하나씩 정렬한다.

void BubbleSort(vector<int>& v)
{
	for (int i = 0; i < v.size() - 1; i++)
	{
		int temp = 0;
		for (int j = 0; j < v.size() - 1 - i; j++) // 이미 정렬 완료된 요소는 스킵
		{
			if (v[j] > v[j + 1])
			{
				temp = v[j];
				v[j] = v[j + 1];
				v[j + 1] = temp;
			}
		}
	}
}

인덱스는 0부터 시작하기 때문에, 인덱스 4번까지 정렬을 하겠다면 벡터의 사이즈보다 1 작은 만큼 정렬해야 한다.

또한 이미 정렬이 완료된 뒤쪽 원소를 스킵하기 위해 안쪽 루프문에서 i 만큼 빼준다.

- 시간 복잡도 : (N - 1) + (N - 2) + ... + 2 + 1 = N(N-1) / 2 = O( N^2 )

 

 

2. 선택 정렬(Selection Sort)

배열 중에 가장 크거나 작은 값을 선택해서 정렬.

이미 정렬한 원소를 제외하고 나머지 원소 중에서 고른다.

이 때 원소를 직접 고르는 것 보다는 인덱스를 고른다는 것이 중요하다.

void SelectionSort(vector<int>& v)
{
	for (int i = 0; i < v.size() - 1; i++)
	{
		int bestIndex = i;

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

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

배열에서 가장 작은 숫자를 bestIndex에 저장하고 배열의 맨 앞에 저장한다.

그리고 정렬이 끝난 원소를 스킵하기 위해 j를 도입한다.

- 시간 복잡도 : (N - 1) + (N - 2) + ... + 2 + 1 = N(N-1) / 2 = O( N^2 )

 

3. 삽입 정렬(Insertion Sort)

원소를 하나 선택해서 정렬된 것으로 둔다.

다음 원소를 선택해서 이미 정렬된 다른 원소보다 크면 그 원소의 뒤에 둔다.

그 다음 원소를 정렬된 다른 원소와 비교해서 크면 그 원소의 뒤에 둔다.

void InsertionSort(vector<int>& v)
{
	for (int i = 1; i < v.size(); i++) // 첫 원소는 정렬된 것으로 간주함
	{
		int insertData = v[i]; // 원소 선택

		int j;
		for (j = i - 1; j >= 0; j--)
		{
			if (v[j] > insertData)	// 선택한 원소가 더 작으면
				v[j + 1] = v[j];    // 비교한 원소를 오른쪽에 저장
			else
				break;              // 선택한 원소가 더 크면
		}
		v[j + 1] = insertData;      // 선택한 원소를 오른쪽에 저장
	}
}

 

- 시간 복잡도 : (N - 1) + (N - 2) + ... + 2 + 1 = N(N-1) / 2 = O( N^2 )