정렬 알고리즘 정리1 ( 개념 / 시간복잡도 - O(n^2) )

안녕하세요! 

오늘은 정렬 알고리즘에 대해 공부하려고 해요.

정렬 알고리즘은 공부를 안하면 늘 까먹는 것 같아요..

퀵정렬이 어떻게 이뤄지는지....선택정렬이 뭐였는지..

또 시간복잡도는 뭔지!!!

공부를 해도 항상 몇달 뒤면 까먹게 되네요 :(

저도 공부를 할 겸 정리하는 시간을 가져볼려고 합니다.

 

1. 선택정렬(selection sort) - O(n²)

먼저 선택정렬의 정의 부터 볼까요?

---

"선택 정렬(selection sort)은 정렬되지 않은 데이터들에 대해 

가장 작은 데이터를 찾아 가장 앞의 데이터와 

교환해나가는 방식이다."

---

라고 하네요 :)

선택정렬에서는 세가지 과정만 기억하시면 됩니다.

1. 앞에서 부터 데이터 하나를 선택한다.

2. 내가 선택한 데이터 이후에 있는 원소들 중 가장 작은 값을 찾는다.

3. 내가 선택한 값과 바꾼다.

말로하니 잘 모르시겠나요?

위키백과에 있는 예제를 통해 알아볼게요 :)

---

[9,1,6,8,4,3,2,0]

1. 앞에서 부터 데이터 하나를 선택한다. --> 9

[9,1,6,8,4,3,2,0]

2. 내가 선택한 데이터 이후에 있는 원소들 중 가장 작은 값을 찾아 --> 0

[9,1,6,8,4,3,2,0]

3. 내가 선택한 값과 바꾼다.  0 <----> 9

[0,1,6,8,4,3,2,9]

한 번 더 해볼까요?

앞에서 부터 데이터를 하나씩 선택하랬죠? 

저희는 맨앞 즉 배열에 첫번째 원소에 대해서는 할 일이 끝났으니

다음 원소 즉, 두번째 원소에 대해서 위와 같은 과정을 반복해주면 된답니다.

1. 앞에서 부터 데이터 하나를 선택한다. --> 1

[0,1,6,8,4,3,2,9]

2. 내가 선택한 데이터 이후에 있는 원소들 중 가장 작은 값을 찾아 --> 1

[0,1,6,8,4,3,2,9]

3. 내가 선택한 값과 바꾼다.  1 <----> 1

[0,1,6,8,4,3,2,9]

이 과정의 경우 내가 선택한 값과 가장 작은 값이 동일하니

배열 안에서는 변화가 일어나지 않은게 당연하겠죠?

한 번만 더 해보겠습니다. 

1. 앞에서 부터 데이터 하나를 선택한다. --> 6

[0,1,6,8,4,3,2,9]

2. 내가 선택한 데이터 이후에 있는 원소들 중 가장 작은 값을 찾아 --> 2

[0,1,6,8,4,3,2,9]

3. 내가 선택한 값과 바꾼다.  6 <----> 2

[0,1,2,8,4,3,6,9]

---

위 과정을 반복하게 되면 오름차순으로 원소들이 정렬되게 된답니다 :)

이제 시간복잡도를 생각해 볼까요?

데이터의 개수가 n개라고 했을 때, 

첫 회전에서의 비교횟수 : 1 ~ n-1 => n-1 

두번째 회전에서의 비교횟수 : 2 ~ n-1 => n-2

.

.

.

(n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

즉, O(n²) 

간단히 말해,

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 O(n²) 만큼의 시간이 걸립니다.

2. 삽입 정렬 (Insertion sort) - O(n²) 

---

"삽입정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 

이미 정렬된 배열 부분과 비교하여, 

자신의 위치를 찾아 삽입함으로써 

정렬을 완성하는 알고리즘입니다."

---

역시 말로하니 이해가 안되네요ㅎㅎ..

예제를 통해 알아보겠습니다. 그전에,

삽입정렬에서 기억하셔야 할 점은 

1. 정렬은 두번째 인덱스부터 시작(선택)한다 --> 처음 정렬을 시작할 때만

why? 첫번째 리스트는 하나이기 때문에 정렬이 되어있다고 보기때문

2. 내가 선택한 원소를 Key에 저장한다.

3. Key와 내가 선택한 이전에 있는 원소들과 비교하며 삽입해나간다.

4. 내가 선택한 원소의 다음 인덱스에 있는 원소를 선택한다.

입니다.

정렬을 시작하는 처음에만 두번째 원소부터 시작하는 것이니

처음을 제외한 나머지 회전은 2~4의 과정을 반복하는 것이 되겠네요 :)

---

[8,5,6,2,4]

1. 두번째 인덱스부터 시작한다 --> 5

[8,5,6,2,4]

2. 내가 선택한 원소를 Key에 저장한다. ---> Key = 5

3. Key와 내가 선택한 이전에 있는 원소들과 비교하며 삽입해나간다.

[8,5,6,2,4]

현재 제가 선택한 것은 두번째 인덱스에 있는 5죠?

그 이전에 있는 원소라 함은 8이네요 :)

그러면 Key(5)와 8을 비교하는 것이 되겠네요.

Key인 5가 더 작으므로 

8의 자리인 첫번째 인덱스에 5를 삽입해줍니다.

[5,8,6,2,4]

마지막으로,

4. 내가 선택한 원소의 다음 인덱스에 있는 원소를 선택한다. --> 6

[5,8,6,2,4]

여기서 실수를 할 수 있는게, 8아니야? 할 수 있겠지만, 

( 현재 5 다음에 있는게 8이라서 )

말씀드렸죠? 정렬은 두번째 인덱스 부터 시작합니다. 

두번째 인덱스 다음에 있는 세번째 인덱스. 즉 6을 선택해주어야 겠죠?

한번 더 해볼게요. 

첫 회전을 제외하고 2~4과정을 반복하는 거라고 말씀드렸죠?

2. 내가 선택한 원소를 Key에 저장한다. ---> Key = 6

3. Key와 내가 선택한 이전에 있는 원소들과 비교하며 삽입해나간다.

[5,8,6,2,4]

그럼 먼저 8부터 Key(6)와 비교해야겠죠?

Key가 8보다 더 작으니 6은 8앞에 들어가겠네요.

아직 넣지말고,

또 5와 비교해봅시다.

5는 6보다 작네요?

그럼 6의 위치는 정해졌네요.

5와 8사이입니다.

즉, 패턴이 보이네요. 

key값보다 작은 값이 나올 때 까지 비교를 하게 됩니다. 

[5,6,8,2,4]

이렇게 반복하면 역시나 오름차순으로 정렬이 된답니다.

이해가 안되신다면,

출처 - 위키백과

위 자료들을 보시면 어느정도 이해가 가실 것 같아요 :)

제가 쉽게 설명드릴려고 생각해봤는데,

딱 제가 선택한 원소를 인형뽑기 집게로 딱!! 뽑았다고 생각하세요.

그리고 뒤는 보지말고 앞의 원소들만 보며 비교하면서,

제가 집은 그 원소를 적절한 자리에 삽입시켜준다고 생각해보세요 :)

삽입정렬에 대한 설명과 자료들은 엄청나게 많으니 

이해가 안되신다면 더 찾아보시는 것을 추천드립니다 ㅠㅠ

삽입정렬의 장단점이 있는데요,

장점 : 구현이 간단하다.

단점 : 배열이 길어질수록 효율이 떨어진다. 

마지막으로 삽입정렬에 대한 시간복잡도를 생각해 볼까요?

최악의 경우 (역으로 정렬되어 있을 경우) 선택정렬과 마찬가지로, 

(n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

즉, O(n²)  이 되겠지만, 

Optimal한 경우, 즉 모두 정렬이 되어있는 경우에는 

한번씩 밖에 비교를 안하므로

O(n) 의 시간복잡도를 가지게 됩니다.

(Ω(n)이 정확한 표현입니다.)

또한

 이미 정렬되어 있는 자료구조에 자료를 하나씩 삽입/제거하는 경우에는

 현실적으로 최고의 정렬 알고리즘이 되는데, 

탐색을 제외한 오버헤드가 매우 적기 때문입니다. 

또한 선택 정렬이나 거품 정렬과 같은 같은 O(n²)  알고리즘에 비교하여 

빠릅니다.

삽입 정렬 내부 반복문은 생각보다 빠르기 때문에 

데이터의 수가 8~20 개 근처일 때 

가장 빠른 정렬 알고리즘이 될 수도 있다고 하네요 :)

그래서 시간복잡도가 뭐냐구요?

하지만 저희가 시간복잡도를 나타내는 빅오 표기법

(Big-O notation)은 최악을 기준으로 하기 때문에 

삽입정렬의 시간복잡도는 O(n²) 이라고 

알고계시면 될 것 같아요ㅎㅎ

3. 버블 정렬 (Bubble Sort)- O(n²) 

버블정렬은  두 인접한 원소를 검사하여 정렬하는 방법이에요. 

버블정렬은 시간복잡도가 O(n²) 으로 상당히 느린편에 속하지만,

코드가 단순해서 자주 사용된다고 합니다 :)

예제를 통해 한번 볼까요? 버블정렬은 정말 쉬우니 

한번에 이해가 가실거에요.

과정을 먼저 살펴볼까요?

1. 앞에서부터 다음 인덱스와 비교한다.(인접한 인덱스끼리 비교)

2. 큰 것은 뒤로 보낸다.

3. 배열의 끝까지 1~2과정을 반복하며, 한 회전이 끝나면 

다시 앞으로 돌아와 1~2의 과정을 반복한다.

---

[6,5,9,3,1]

1. 앞에서부터 다음 인덱스와 비교한다.

[6,5,9,3,1]

2. 큰 것은 뒤로 보낸다.

[5,6,9,3,1]

첫번째 인덱스에 관해 정렬이 끝났으니 

이제 두번째 인덱스에서 시작해 

인접한 인덱스, 즉 다음 인덱스와 비교해야겠죠?

1. 앞에서부터 다음 인덱스와 비교한다.

[5,6,9,3,1]

2. 큰 것은 뒤로 보낸다.

[5,6,9,3,1]

1. 앞에서부터 다음 인덱스와 비교한다.

[5,6,9,3,1]

2. 큰 것은 뒤로 보낸다.

[5,6,3,9,1]

1. 앞에서부터 다음 인덱스와 비교한다.

[5,6,3,9,1]

2. 큰 것은 뒤로 보낸다.

[5,6,3,1,9]

자, 이렇게 한 회전이 끝났습니다. 

이제 처음으로 ( 첫번째 인덱스로 ) 돌아가 위 과정을 반복해주면

최종적으로 오름차순으로 정렬이 되게 된답니다 :)

---

버블정렬의 시간복잡도를 생각해볼까요?

시간복잡도는

(n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

즉 O(n²)라고 할 수 있겠네요.

선택정렬과 마찬가지로 배열이 어떻게 되어있든 

비교를 진행하니 O(n²)이 맞겠죠?

버블 정렬은 한번의 순회를 마칠 때 마다 비교 대상이 하나씩 줄어들기 때문에, 

->  why? 한 회전이 끝나면 배열안에서 가장 큰 값이 맨 뒤로 가기 때문.

전체 원소의 개수가 n개 라고 할 때, 총 n-1 번 순회하면 정렬이 끝납니다. 

위의 예제에서는 총 원소 개수가 5개 이므로,

 4 + 3 + 2 + 1 = 10번 비교하게 됩니다.

자, 오늘은 O(n²) 정렬 알고리즘들을 살펴봤는데요,

원래 모든 정렬 알고리즘을 하나의 글에 정리하려다 너무 길어질 것 같아서

시간복잡도로 나눠서 정리하려고 합니다 XD

 O(n²)정렬 알고리즘엔

선택정렬, 삽입정렬, 버블정렬이 있다는것.

잊지마세요!!

그리고 사실 이 글에는 쓰지않았지만, 

퀵소트도 빅오표기법으로 시간복잡도를 O(n²)을 가지는 정렬 알고리즘입니다.

위에서 말씀드렸듯이, 빅오표기법(Big-O notation)은 

최악의 수행시간으로 말해야 합니다 :)

궁금증이 드실 수 도 있겠네요.

"퀵소트 O(nlogn)아니야?"

이 말은 사실 정확히 맞는말은 아닙니다.

왜 정확히 맞는 말이 아닌지 생각하기전에,

---

"시간복잡도"

---

혹시 "시간복잡도"의 정의를 아시나요?

시간복잡도는

간단히 말해서 

"어떤 알고리즘이 얼마나 걸리느냐"

라고 할 수 있습니다. 

이 시간복잡도를 구하는 방법은

시간 복잡도  = 알고리즘을 구성한 명령어가 실행된 횟수

(frequency of calling command)

라고 정의할 수 있습니다. 

frequency of calling command는 

frequency count라고도 한답니다.

원래 시간복잡도는 

시간복잡도 = 

알고리즘을 구성한 명령어가 실행된 횟수(frequency count)  

+ 

 명령어 실행시간(execution time)

입니다. 

하지만 이 명령어 실행시간(execution time)은 

특정 하드웨어 또는 사용 언어에 따라서 값이 달라질 수 있기때문에

일반적인 시간복잡도는 명령어 실행시간을 제외한 

명령어가 실행된 횟수(frequency count)만을 고려하게 됩니다.

또한 시간복잡도에도 종류가 있다는 것. 아시죠?

시간복잡도는 나타내는 방법으로는 세가지가 있습니다. 

O() - 빅오

Ω() - 오메가

Θ() - 세타

간단히 말해서

O() - 빅오 -> 최악시간

Ω() - 오메가 -> 최상시간

Θ() - 세타 -> 평균시간

입니다.

 

설명을 붙이자면,

O(). 빅오표기법(Big-O notation)은 

가장 일반적으로 많이 쓰이는 시간복잡도 표기법입니다. 

즉, 알고리즘 실행시간의 상한을 나타내는 표기법이죠.

Ω(). 오메가표기법은 알고리즘 실행시간의 하한을 나타내는 표기법입니다.

Θ(). 세타표기법은 알고리즘 실행시간의 평균시간을 나타내는 표기법입니다. 

 

시간복잡도에 대한 설명이 길어졌네요 ㅎㅎ..

본론으로 돌아와서!!  

왜 퀵소트의 시간복잡도 O(nlogn)이 틀린말일까요?

위에 퀵소트에 대한 설명이 없어서 아직 퀵소트가 무엇인지 잘 모르시겠지만,

이것 하나만 알아두세요.

 

퀵소트에 대한 시간복잡도는

평균복잡도는 nlogn이지만 최악의 경우엔 n²이므로,

 빅오표기법으로 표현한다면 시간복잡도는 O(n²)입니다.

왜 최악인지는 다음 글에서 설명할게요.

그럼 퀵소트를 nlogn의 시간복잡도로 표현하고 싶다면,

평균복잡도가 nlogn이니

Θ(nlogn)이 되겠네요.

뭔가 위에서 시간복잡도 다 말해놓고 

밑에서시간복잡도의 정의를 설명하는게 좀 웃길 수도 있는데,

퀵소트를 말하다보니 이렇게 됐네요..ㅎㅎ

퀵소트의 시간복잡도에는 함정이 있으니 조심하세요!!

ps. 퀵소트를 이 글에 추가해야할지, 아니면 다음 글에 추가해야 할지 고민하다가 (왠지 여기에 추가하는 게 맞는 것 같지만)여기에 설명하게 되었네요

ㅎㅎ..

 

${\displaystyle \frac{\mathrm{<br>}}{}}$