알고리즘 - 정렬

Sort Algorithm 

 

사실  대부분의  프로그래밍 언어에서는 sort메서드를 제공한다  하지만   우리가 정렬 알고리즘을 배워야 하는 이유는  내가 가진 데이터 베이스의  양이나   상황에 따라 어떤  정렬을 사용하는 것이 좋을지 달라지기 때문에  우리는 기본적으로  유명한  정렬 알고리즘 들을 알고 있어야 할 것이다 

 

 

1. Bubble Sort

 

가장  먼저 버블 정렬이다  버블 정렬은  마치 거품이 일어나듯이  연쇄적으로  자기 자리를 찾아간다고 하여  버블 정렬이라는 이름이 붙여졌다  

 

 

위 그림을 보면 알 수 있듯이  데이터를  두개를  묶어서 비교한 후  크기가  큰 쪽이 오른쪽으로  가도록  자리를 

바꿔가면서  크기가 큰 데이터를 오른쪽으로 민다  그러면 1회전이 끝남과 동시에  이 리스트에서 가장 큰값이 가장 오른쪽으로 위치한다  즉  n번째 정렬 회차가 끝나면 뒤에서  n번째  자리의  데이터가 확정된다 

 

Big O

버블 정렬은  최악의 경우에  O(n ^ 2)의  시간 복잡도를 가진다  왜냐하면 각 자리를 찾기 위해서 n번의 순회를 해야하며 n번의 회전 동안에  요소의 개수만큼 또 순회를 해야하기 때문이다  그러나 이미 정렬이 되어 있는 경우에는 하번의 순회로 정렬 여부를 알 수 있다

 

장점 

버블 정렬은 in place 알고리즘이기 때문에  메모리가 절약된다  여기서  in place란  자료를 정렬할 때 추가적인 메모리 공간이 필요한 것이 아니고 데이터가 저장된 그 공간 내에서 정렬을 한다는 뜻이다 또한 구현하기 매우 쉽다는 장점이 있다 

 

단점 

버블 정렬의 가장 큰 단점은 자료의 개수가 많아질수록 성능이 매우 떨어진다는 점이다 왜냐하면 최악의 경우 O(n^2)이 소요되기 때문이다  

 

코드로 구현한  버블 정렬 예제 

 

                                                            ex) 결과

 

2. Insertion Sort

삽입 정렬은 왼쪽에서  오른쪽으로 가면서  각 요소들을  왼쪽 요소들과 비교하면서 알맞은 자리에 삽입하는 형식의 정렬 방법이다 

 

 삽입 정렬은  위 그림처럼  항상 두 번째  요소를  왼쪽  요소와  비교하면서  시작한다  1회전에서는 왼쪽 요소 보다 두번째 요소가 크기 때문에 아무런 일이 일어나지 안흔ㄴ다 2회전에서는 2를 왼쪽 두개의 데이터와 비교하여 가장 왼쪽에 끼워넣는다 3회전에서는 5를 왼쪽 데이터와  비교하여 3과 7사이에 끼워 넣는다  이런식으로 회전을 하다보면 정렬이 되는 방식이다 삽입 정렬은  항상 왼쪽 비교대상 데이터들이 정렬되어 있다는 가정하에 진행된다 

 

Big O

삽입 정렬 역시  버블 정렬과  같은 시간 복잡도를 가진다 

 

장점 

삽입 정렬도  버블 정렬과  같이  in place 알고리즘이기 때문에  메모리가 절약된다는 장점이 있다 

또한 구현하기 매우 쉽고  이미 정렬된  데이터를 순회하는 경우  O(n)번만 순회하면 되기 때문에 

정렬이 되었는지  안되었는지  테스트 하는 용도로 사용될 수 있다 

 

단점 

삽입 정렬도 버블 정렬과 같은  시간 복잡도를 가지기에  데이터가 많아지면  성능이  떨어진다는 단점이 있다 

 

 

코드로 구현한  삽입 정렬 

 

                                                 ex)  결과  화면 

 

 

                                                   

3. Selection Sort 

선택 정렬은  매우 단순한  정렬 알고리즘으로  구현하기 매우 쉬운 알고리즘ㅇ다 

다음과 같은 흐름으로  진행된다 

 

1. 먼저  주어진 리스트 중에  최소값을 찾는다 

2. 그 값을 맨 앞에 위치한 값과  교환한다

3 이제 맨 앞을 제외하고 다시 순회하며 최소값을 찾는다

4 그 값을  맨 앞 위치 바로 다음 위치와 교체한다 

 

버블 정렬은 각 회전이 끝날 때마다 맨 마지막 데이터의  위치가 정해졌다면 

선택 정렬은  n번째  회전이 끝날 때마다  앞에서 n번째 데이터의  위치가 정해진다 

 

 

Big O

선택 정렬은  위의  두 정렬과는 다르게  이미 정렬이 되었는 경우에도 O(n^2)의 시간 복잡도를 가집니다  이유는  매번 정해진 자리에 올 수 있는 최소값을  찾아야 하기 때문이다 

 

장점

선택 정렬도  위의  두 정렬과 같이  in place 알고리즘이기 때문에  메모리가 절약된다는 장점이 있으며 알고리즘이 직관적이여서  쉽고 구현하기도 쉽다 

 

단점 

선택 정렬은 최선의  경우에도 최악의 경우에도  O(n ^ 2)의  시간이 걸리는 만큼  성능이 떨어진다 

 

 

코드로 구현한  선택 정렬 

                                     ex)  결과  화면 

 

 

 

1회전만에  정렬이  되었으나 선택 정렬은  데이터가 정렬된 상태 에서도 계속 순회하며 최솟값을 찾는 과정을 반복한다  이것을 통해  비효율적인 정렬임을 알 수 있다