본문으로 바로가기

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

category Development/Algorithm 2016.04.01 12:32

정렬 알고리즘


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


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


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


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


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


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


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


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


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




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


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


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


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





1. 삽입정렬(Insertion Sort)


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


3. 선택정렬(Selection Sort)


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


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



1. 삽입정렬(Insertion Sort)



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


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


대상 리스트 : [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)



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


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


대상 리스트 : [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)



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


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 단위의 성능을 내는 알고리즘들이 있는데,


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


댓글을 달아 주세요