정렬 알고리즘 (버블, 삽입, 선택)

오늘은 정렬 알고리즘에 대해 알아보도록 하겠습니다.

---

1. 개요

많은 컴퓨터 과학자들은 어떻게하면 좀더 쉽고 빠르게 배열을 정렬할수있는지에 대해 많은 연구를 하였습니다.
그 중에서 빠르진 않지만 쉬운 정렬인 (버블, 삽입, 선택) 정렬 에대해 알아보도록 하겠습니다.

---

2. 버블 정렬(Bubble Sort)

버블정렬은 선택정렬과 유사합니다. 서로 인접한 두 원소를 비교하고, 조건에 맞지않으면 자리를 교환하는 알고리즘입니다.
매우 쉬운 알고리즘 입니다.
버블 정렬의 과정은 다음과 같습니다.

1. 1화전에 첫 번쨰 원소와 두 번째 원소 비교 다시 두 번째 원소와 세 번쨰 원소의 비교 점점 나아가 마지막 원소 -1 과 비교하여 조건이 맞지 않으면 서로 자리를 변경한다.
2. 1회전을 수행하고 나면 가장 큰 수가 맨 뒤 원소로 향하고 2회전 정렬에서는 마지막 원소는 정렬에서 제외되며 이것을 회전마다 반복하면 데이터가 점점 정렬되는 형태가 됩니다.

(Source)

void BubbleSort(int arr[], int length)
{
	int temp = 0;
	for (int i = 0; i < length; i++)
	{
		for (int j = 1; j < length; j++)
		{
			if (arr[j-1] > arr[j])
			{
				temp = arr[j - 1];
				arr[j - 1] = arr[j];
				arr[j] = temp;
			}
		}
	}

}

이러한 코드가 나옵니다.
 

출처 : https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html

시간 복잡도

시간복잡도는 최악 최선 평균 다 O(N^2) 나옵니다 별로 좋지 않는 시간복잡도입니다.

장점

• 구현이 매우 간단하고, 소스코드가 직관적이다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않다. => 제자리 정렬(in-place sorting)
• 안정 정렬(Stable Sort) 이다.

 

단점

• 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적이다.
• 정렬 돼있지 않은 원소가 정렬 됐을때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 된다.

---

3. 선택 정렬(Selection Sort)

선택정렬은 버블정렬과 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 입니다.
 
선택 정렬과 삽입 정렬을 헷갈려하는 사람들이 종종 있는데, 선택 정렬은 배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것 이라고 생각하면 편하다.
 
선택 정렬의 과정은 다음과 같습니다.

1. 주어진 배열 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다. Pass
3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

void SelectSort(int arr[], int length)
{
	int indexMin, temp;
	for(int i=0;i<length-1;i++)
	{
		indexMin = i;
		for(int j=i+1;j<length;j++)
		{
			if(arr[j]<arr[indexMin])
			{
				indexMin = j;
			}
		}

		temp = arr[indexMin];
		arr[indexMin] = arr[i];
		arr[i] = temp;
	}
	
}

1. 우선, 위치(index)를 선택해준다.
2. i+1 번째 원소부터 선택한 위치(index)의 값과 비교를 시작한다.
3. 오름차순이므로 현재 선택한 자리에 있는 값보다 순회하고 있는 값이 작다면, 위치(index)를 갱신해준다.
4. 2번 반복문이 끝난 뒤에는 indexMin에 1번에서 선택한 위치(index)에 들어가야하는 값의 위치(index)를 갖고 있으므로 서로 교환(swap)해준다.

출처 : https://gyoogle.dev/blog/algorithm/Selection%20Sort.html

시간 복잡도

최선 최악 평균 전부 O(n^2) 나온다
 

장점

• Bubble sort와 마찬가지로 알고리즘이 단순하다.
• 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.
• Bubble Sort와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)

 

단점

• 시간복잡도가 O(n^2)으로, 비효율적이다.
• 불안정 정렬(Unstable Sort) 이다.

---

4. 삽입 정렬(Insertion Sort)

손 안의 카드를 정렬하는 방법과 유사
 
삽입 정렬은 선택 정렬이랑 비슷하지만, 좀 더 효율적인 정렬 알고리즘이다.
 
삽입 정렬은 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 저장한 후, 원소를 뒤로 옳기고 지정된 자리에 자료를 삽입 하여 정렬하는 알고리즘
 
최선의 경우 O(N) 이라는 엉청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬이다.
 
삽입정렬의 과정은 이러하다.

1. 정렬은 2번째 위치(index)의 값을 temp에 저장한다.
2. temp와 이전에 있는 원소들과 비교하며 삽입해나간다.
3. 1번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다.

void InsertionSort(int arr[],int length)
{
	for(int index = 1; index<length;index++)
	{
		int temp = arr[index];
		int prev = index - 1;
		while((prev>=0)&&(arr[prev]>temp))
		{
			arr[prev + 1] = arr[prev];
			prev--;
		}
		arr[prev + 1] = temp;
	}
}

1. 첫 번째 원소 앞(왼쪽)에는 어떤 원소도 갖고 있지 않기 때문에, 두 번째 위치(index) 부터 탐색을 시작한다. temp에 임시로 해당 위치(index)값을 저장하고, prev에는 해당 위치(index)의 이전 위치(index)를 저장한다.
2. 이전 위치(index)를 가리키는 prev가 음수가 되지않고, 이전 위치(index)의 값이 1번에서 선택한 값보다 크다면, 서로 값을 교환해주고 prev를 더 이전 위치(index)를 가리키도록한다.
3. 2번에서 반복문이 끝나고 난 뒤, prev에는 현재 temp 값보다 작은 값들 중 제일 큰 값의 위치(index)를 가리키게 된다. 따라서, (prev+1)에 temp값을 삽입해준다.
   
   

출처 : https://gyoogle.dev/blog/algorithm/Insertion%20Sort.html

시간복잡도

최악 평균은 버블 선택과 마찬가지로 O(N^2)이다. 하지만 최선일 경우O(N)이다.

장점

• 알고리즘이 단순하다.
• 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)
• 안정 정렬(Stable Sort) 이다.
• Selection Sort나 Bubble Sort과 같은 O(n^2) 알고리즘에 비교하여 상대적으로 빠르다.

 

단점

• 평균과 최악의 시간복잡도가 O(n^2)으로 비효율적이다.
• Bubble Sort와 Selection Sort와 마찬가지로, 배열의 길이가 길어질수록 비효율적이다.

---

5. 요약

종류	시간복잡도	안정 vs 불안정
버블	전부 O(N^2)	안정
삽입	전부 O(N^2)	불안정
선택	최악, 평균 O(N^2) 최선 O(N)	안정

---

6. Ref

https://gyoogle.dev/blog/

👨🏻‍💻 Tech Interview