정렬

선택 정렬 (Selection Sort)

핵심

전체에서 가장 작은 수를 선택해 가장 앞으로 보낸다.

진행

전체에서 가장 작은 수를 검색
맨 앞의 숫자와 위치를 바꾼다.
정렬이 완료된 첫 번째 수를 제외한 나머지 수에서 정렬
…
같은 방법으로 정렬이 끝날 때까지 반복

구현

int main(void)
{
	int i, j, min, index, temp;
	int array[10] = {1, 10, 5, 8, 7, 6, 5, 4, 3, 2, 9};
	
	for (i = 0; i < 10; i++)
	{
		min = 9999; /* 가장 큰 원소보다 큰 값을 넣어준다. */
		for (j = i; j < 10; j++)
			if (min > array[i]) /* 현재 탐색하는 원소가 현재 최소값보다 작으면 */
			{
				min = array[j]; /* 최소값을 현재 탐색하는 원소로 바꾼다. */
				index = j; /* 최소값을 가진 배열 순서를 index에 저장 */
			}
		/* 가장 앞에 위치한 수와 최소값을 swapping */
		temp = array[i];
		array[i] = array[index];
		array[index] = temp;
		/* swapping 종료 */
	}
	for (i = 0; i < 10; i++)
		printf("%d ", array[i]);
	return (0);
}

O(N^2)

1 2 3 4 5 6 7 8 9 10

정렬하려면

1부터 10까지 확인 (10번)
가장 작은 값을 맨 앞으로
2부터 10까지 확인 (9번)
2번 반복
…
끝까지 반복

10 + 9 + … + 1 (등차수열)
=> 10 * (10 + 1) / 2 = 55
=> N * (N + 1) / 2
=> O(N * N)

고로, 시간 복잡도는 O(N^2)이다.

버블 정렬 (Bubble Sort)

핵심

인접한 두 수를 비교한 후, 더 작은 수를 선택해 앞으로 보낸다.

진행

맨 앞의 두 수 중 더 작은 수를 앞 순서로 보낸다.
(1회전 시 10이 맨 뒤로 감)
마지막 수를 제외하고 비교&정렬
…
끝까지 반복

구현

int main(void)
{
	int i, j, temp;
	int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};

	for (i = 0; i < 10; i++)
		for (j = 0; j < 9 - i; j++) /* 1회전마다 집합의 크기를 1 감소 */
			if (array[j] > array[j + 1]) /* 왼쪽 값이 오른쪽 값보다 크면 */
			{
				/* 양쪽의 값을 swapping */
				temp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temp;
				/* swapping 종료 */
			}
	for (i = 0; i < 10; i++)
		printf("%d ", array[i]);
	return (0);
}

O(N^2)

시간 복잡도는 선택 정렬과 동일하지만, 버블 정렬은 매 순간 자리를 바꾸는 연산을 수행하기 때문에 훨씬 많은 작업을 수행하게 되어 작업 시간이 훨씬 느리다.

1 2 3 4 5 6 7 8 9 10

정렬하려면

1부터 10까지 두 수를 비교하면서 위치 조정 (9번)
1부터 9까지 비교 (8번)
…
끝까지 반복

9 + 8 + 7 + … + 1 (등차수열)
=> 9 * (9 + 1) / 2
=> (N - 1) * N / 2
=> O(N * N)

삽입 정렬 (Insertion Sort)

핵심

각 숫자를 적절한 위치에 삽입한다.
다른 정렬과 달리 필요할 때만 자리를 바꾼다.

진행

1 10 5 8 7 6 4 3 2 9 를 오름차순 정렬한다면?

1은 정렬할 위치가 없음
(1 앞에 숫자가 없으므로)
10은 1보다 크기 때문에 위치 유지
_ 1 _ 10 언더바 두 자리 중 한 군데에 들어갈 수 있음
5는 1보다 크고 10보다 작기 때문에 해당 위치로 이동
(10과 자리를 바꿈)
_ 1 _ 10 _ 5 세 자리 중 한 군데에 들어갈 수 있다.
이런 식으로 반복

구현

int main(void)
{
	int i, j, temp;
	int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};

	for (i = 0; i < 9; i++)
	{
		j = i;
		while (array[j] > array[j + 1])
		{
			temp = array[j];
			array[j] = array[j + 1];
			array[j + 1] = temp;
			j--;
		}
	}
	for (i = 0; i < 10; i++)
		printf("%d ", array[i]);
	return (0);
}

O(N^2)

선택 정렬, 버블 정렬과 시간 복잡도가 동일한 이유는 최악의 경우에 연산이 많아지기 때문이다.
정렬이 잘 되어 있는 경우에는 가장 연산이 적게 일어나고 자원을 적게 소모하며 빠르다.
후에 나올 퀵 정렬 등과 비슷하거나 더 나은 퍼포먼스를 보여준다.

효율적인 이유 : 정렬 해야 하는 특정 숫자의 앞 숫자들은 정렬이 완료된 상태이므로 전체를 비교하지 않고 해당 숫자의 왼쪽 숫자부터 비교하면서 큰 값이 왼쪽에 있을 때 위치를 바꿔주면 됨.

1 5 7 8 10 6 .. 에서 6을 10부터 7까지 3번만 비교하면서 위치를 바꿔주면 1 5 6 7 8 10.. 으로 정렬

퀵 정렬 (Quick Sort)

핵심

대표적인 분할 정복 알고리즘.
특정 값을 기준으로 큰 숫자와 작은 숫자를 나눈다.

진행

3 7 8 1 5 9 6 10 2 4
오름차순으로 정렬하려면

보통 첫 번째 원소를 기준 값(= Pivot)으로 설정
왼쪽에서 오른쪽으로 가며 피벗 값보다 큰 값을 찾고, 오른쪽에서 왼쪽으로 오며 피벗값보다 작은 값을 찾는다.

큰 값 : 7, 작은 값 : 2
큰 값과 작은 값의 위치를 바꾼다.

(3) 2 8 1 5 9 6 10 7 4
반복하면
(3) 2 1 8 5 9 6 10 7 4
큰 값과 작은 값을 찾는다.

큰 값 : 8, 작은 값 : 1
작은 값의 인덱스가 큰 값의 인덱스보다 작은 경우(엇갈린 경우), 작은 값과 가장 왼쪽 값의 위치를 바꾼다.
(이제 3은 정렬이 완료되었고 3의 왼쪽은 3보다 작은 수, 오른쪽은 3보다 큰 수의 집합이 됨 = 집합을 한 번 분할)

1 2 3 8 5 9 6 10 7 4
1회전 후에는 기준 값 왼쪽은 기준값보다 작고, 오른쪽은 기준값보다 크다.
작은 값의 집합과 큰 값의 집합 각각에서 첫 번째 수가 피벗값이 된다.

(1) 2 3 (8) 5 9 6 10 7 4
작은 값의 집합과 큰 값의 집합에서 각각 정렬을 수행
작은 값의 집합에서의 정렬

큰 값 : 2, 작은 값 : 1 (없으므로 자기 자신을 고름)
엇갈렸으므로 1과 자기 자신의 위치를 바꾼다.
1 2 3
큰 값을 기준으로 피벗을 수행
1 (2) 3
데이터가 2밖에 없으므로 확정
1 2 3
큰 값의 집합에서의 정렬

큰 값 : 9, 작은 값 : 4
(8) 5 4 6 10 7 9
큰 값 : 10, 작은 값 : 7
(8) 5 4 6 7 10 9
(7) 5 4 6 8 (10) 9
또 양 옆의 집합들을 각각 정렬 반복

구현

#include <stdio.h>

int number = 10;
int data[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};

void quickSort(int *data, int start, int end) {
	int pivot = start;
	int i = start + 1;
	int j = end;
	int temp;

	if (start >= end) // 원소가 1개인 경우
		return;

	while (i <= j) // 엇갈릴 때까지 반복
	{
		while (data[i] <= data[pivot]) // 키 값보다 큰 값을 만날 때까지
			i++; // 오른쪽으로 이동
		while (data[j] >= data[pivot] && j > start) // 키 값보다 작은 값을 만날 때까지
													// start 값을 넘어가면 pivot값이 나오고, 그 이상은 가면 안되니까 조건을 걸어줌
			j---;
		if (i > j) // 현재 엇갈린 상태면 키 값과 교체
		{
			temp = data[j];
			data[j] = data[pivot];
			data[pivot] = temp;
		}
		else
		{
			temp = data[j];
			data[j] = data[i];
			data[i] = temp;
		}
	}
	quickSort(data, start, j - 1); // 재귀함수
	quickSort(data, j + 1, end); // pivot이 바뀔 때마다 분할 정렬을 해야하니까
}

int main(void)
{
	quickSort(data, 0, number - 1);
	for (int i = 0; i < number; i++)
		printf("%d ", data[i]);
}

O(N * logN)이지만 최악의 경우 O(N^2)

잘게 쪼갠 후, 각자 정렬하고 다시 합치기 때문에 훨씬 적은 수만큼의 연산을 한다.
데이터 개수 N과 큰 수와 작은 수의 집합으로 계속 반 씩 나눈다는 의미에서 log₂N이라고 볼 수 있다.

1 2 3 4 5 6 7 8 9 10
선택 정렬 : N^2 = 10 * 10 = 100
1 2 3 4 5 / 6 7 8 9 10
(5 * 5 = 25) + (5 * 5 = 25) = 50

이미 정렬이 되어 있거나 거의 정렬이 되어 있는 경우의 시간 복잡도는 O(N^2)

(1) 2 3 4 5 6 7 8 9 10
큰 값 : 10, 작은 값 : 2
1 2 3 4 5 6 7 8 9 10

이런 식으로 분할 정렬의 이점을 사용하지 못하고 하나씩 정렬된다.
반면 삽입 정렬은 이럴 때 굉장히 빨리 동작한다.
그러니 모든 상황에서 가장 빠른 알고리즘이란 없고, 정렬할 데이터의 특성에 따라 적절한 알고리즘을 선택해야 한다.

힙 정렬 (Heap Sort)

이전오류