정렬(Sorting) 알고리즘 O(n^2)

정렬 알고리즘

컴퓨터분야 전공을 했다면 한번쯤 반드시 들어봤을법한 "정렬" 에 관하여 얘기를 하고자 한다.

앞선 포스팅(이라고 해도 몇개월 전에 쓴..) 에서 잠깐 언급을 했었는데, 자세하게 보지않고 스쳐간 것 같아서

정리할 겸 글을 끄적여본다.

사실 간략하게 요약하면 "이진탐색(Binary Search)을 사용하기 위해 데이터를 정렬한다." 의 의미가 클 수 있다.

분산된 데이터는 자료를 참조하기가 어렵다.

예를 들어 100만개의 데이터가 있고, 맨 마지막에 데이터가 있다면, 원하는 데이터를 찾기 위해서는 100만개를 다 봐야할 수 있다.

그렇기 때문에 최악의 경우 n번 탐색을 해봐야 한다.

하지만 이진탐색을 사용하면  의 속도로 검색할 수 있다.

별로 체감이 안될 수 있는데, 다음 그래프를 보면 이해가 쉬울 듯 하다.

이는 데이터의 수가 많을 수록 훨씬 더 효율적이 된다.

(탐색에 관련된 포스팅도 나중에 다시 해야함)

그렇기 때문에 분포되어 있는 데이터를 오름차순(ASC) 혹은 내림차순(DES)으로 정렬해놓는다.

가장 간단한 정렬 알고리즘을 살펴보면

---

1. 삽입정렬(Insertion Sort)

2. 버블정렬(Bubble Sort, 어디서 보니 거품정렬 이러던데.. 걍 버블정렬로 합시다.. 오글오글)

3. 선택정렬(Selection Sort)

정도가 되는데 이 정렬 알고리즘들은 O(n^2) 의 성능을 가지고 있다.

최악의 경우 100개의 데이터가 있다고 했을 때 연산을 10000번을 할 수 있다는 소리

---

1. 삽입정렬(Insertion Sort)

void insertion_sort ( int *data, int n ) { int i, j, remember; for ( i = 1; i < n; i++ ) { remember = data[(j=i)]; while ( --j >= 0 && remember < data[j] ) data[j+1] = data[j]; data[j+1] = remember; } }

"작은 원소를 골라 앞쪽부터 정렬시킨다" 라는 개념으로 접근하면 된다.

배열을 두 개로 나눈다. (물리적으로 나누는 것이 아니라, 개념 상 두개로 나눈다고 보는게 이해가 쉽다)

대상 리스트 : [1, 4, 5, 2, 9, 6 ] 

[1, 4, 5, 2, 9, 6 ] => 순차적으로 정렬을 할 것인데, 1이 가장 먼저나왔으므로 왼쪽 리스트로 간주

[1] [4, 5, 2, 9, 6 ] => 다음은 4를 정렬해야 하는데, 왼쪽 리스트에 1이 있으니 1 다음에 넣는다.

[1, 4] [5, 2, 9, 6] => 다음은 5의 정렬, 4 다음으로 넣는다.

[1, 4, 5] [2, 9, 6] => 다음은 2의 정렬, 1 다음으로 넣는다.

[1, 2, 4, 5] [9, 6] => 다음은 9의 정렬, 5 다음으로 넣는다.

[1, 2, 4, 5, 9] [6] => 다음은 6의 정렬, 5 다음으로 넣는다.

[1, 2, 4, 5, 6, 9] 정렬 끝

---

2. 선택정렬(Selection Sort)

void selectionSort(int *list, const int n) { int i, j, indexMin, temp; for (i = 0; i < n - 1; i++) { indexMin = i; for (j = i + 1; j < n; j++) { if (list[j] < list[indexMin]) { indexMin = j; } } temp = list[indexMin]; list[indexMin] = list[i]; list[i] = temp; } }

"가장 작은 값을 골라 맨 앞부터 자리를 바꾼다" 라는 개념으로 접근하면 된다.

사실 선택정렬과 삽입정렬이 헷갈릴 수 있을만큼 비슷한 로직을 지니고 있다.

대상 리스트 : [1, 4, 5, 2, 9, 6 ] 

[1, 4, 5, 2, 9, 6 ] => 가장 작은 값 선택 : 1을 맨 앞으로

[1] [4, 5, 2, 9, 6] => 가장 작은 값 선택 : 2를 1 뒤로

[1, 2] [4, 5, 9, 6] => 가장 작은 값 선택 : 4를 2 뒤로

[1, 2, 4] [5, 9, 6] => 가장 작은 값 선택 : 5를 4 뒤로

[1, 2, 4, 5] [9, 6] => 가장 작은 값 선택 : 6을 5 뒤로

[1, 2, 4, 5, 6] [9] => 가장 작은 값 선택 : 9를 6 뒤로

[1, 2, 4, 5, 6, 9] 정렬 끝

---

3. 버블정렬(Bubble Sort)

void selectionSort(int *list, const int n) { int temp[6] = {1, 4, 5, 2, 9, 6}; int tempCount = 6; int hold=0, loop, i; for (loop = 0; loop < tempCount - 1; loop++) { for (i = 0; i < tempCount - 1 - loop; i++) { if (temp[i] > temp[i+1]) { hold = temp[i]; temp[i] = temp[i+1]; temp[i+1] = hold; } } } for (i = 0; i < tempCount; i++) { printf("%d", temp[i]); }

"두 원소를 비교해서 가장 큰 값을 맨 뒤로 보내면서 정렬" 이라고 접근하면 쉽다.

if 왼쪽 요소 > 오른쪽 요소 일 때 두 위치를 바꾼다.

else 그대로 놔둔다.

대상 리스트 : [1, 4, 5, 2, 9, 6 ] 

[1, 4, 5, 2, 9, 6] => 맨 앞으로 1,4를 비교, 그대로 놔둔다.

[1, 4, 5, 2, 9, 6] => 4, 5를 비교, 그대로 놔둔다.

[1, 4, 5, 2, 9, 6] => 5, 2를 비교, 왼쪽 요소가 더 크므로 위치를 바꾼다.

[1, 4, 2, 5, 9, 6] => 5, 9를 비교, 그대로 놔둔다.

[1, 4, 2, 5, 9, 6] => 9, 6을 비교, 왼쪽 요소가 더 크므로 위치를 바꾼다.

[1, 4, 2, 5, 6, 9] 1회 정렬 끝 9가 제일 크므로 맨 뒤로 정렬이 되었다.

이 것을 배열요소의 수만큼 반복하면 맨 뒤로 순차적으로 정렬이 된다.

1회차는 0번째 ~ 5번째 요소

2회차는 0번째 ~ 4번째 요소

3회차는 0번째 ~ 3번째 요소

4회차는 0번째 ~ 2번째 요소

5회차는 0번째 ~ 1번째 요소

6회차는 0번째 ~ 0번째 요소

까지 정렬을 한다.

for(int i=0; i<size-i; i--) 라고 생각하면 이해가 될 것이다.

1회차 : 9

2회차 : 6

3회차 : 5

4회차 : 4

5회차 : 2

6회차 : 1

순으로 위치에 맞게 정렬이 된다.

버블정렬 같은 경우는 회차별로 정렬이 어떻게 되는지 잘 알아야할 필요가 있다(필기 및 면접문제로 단골등장.. 이 뿐만 아니라 삽입, 선택정렬도 마찬가지)

위의 배열과 다른 예 입니다 정렬 방식만 보시면 될듯

---

이것들은 가장 간단한 정렬 방식인만큼 효율적이라고 보긴 어렵다.

이보다 빠른 정렬 알고리즘은 현재로써는 log 단위의 성능을 내는 알고리즘들이 있는데,

다음 포스팅에서 이어서 리뷰해야겠다..