정렬알고리즘

얼마 전 , 정렬알고리즘의 공부 필요성을 느끼고 이 글을 정리한다.

정렬 알고리즘

정렬알고리즘이란 원소들을 번호 순이나 사전순서대로 일정한 순서대로 열거하는 알고리즘 을 말한다. 이때 두 조건을 만족해야하는데,
1. 출력은 비 내림차순
2. 출력은 입력을 재배열하여 만든 순열이다.

예를 들어 [ 5, 3, 4, 1, 6, 2 ] 이라는 배열이 있을 경우, 결과값은 [1, 2 ,3 ,4 ,5 ,6] 이 나오도록 일련의 과정을 거친다.
이 과정을 우리는 정렬알고리즘이라고 부르며 이에 해당하는 조사된 정렬알고리즘의 종류는

삽입, 선택, 합병, 힙, 퀵,타임.......

1956년 거품정렬 분석과 더불어 지금까지도 발명되고 발견되고 있다. 많은 정렬알고리즘을 알고 있으면 좋으나.. 기본적인 5가지의 정렬알고리즘인 선택 / 삽입 / 버블 / 합병 / 퀵 정렬에 대해서 알아보도록 하자.
https://www.youtube.com/watch?time_continue=45&v=kPRA0W1kECg&feature=emb_logo

<정렬알고리즘을 설명해주는 재밌는 영상>

선택 정렬 ( Selection Sort )

선택정렬은 첫번째 원소를 마지막 원소까지 차례대로 비교를 하며, 가장 작은 값을 찾아 해당 원소와 자리를 바꾼다.
예를 들어 [ 2, 1, 7, 6, 3, 5] 이라는 배열이 있다고 가정한다면 정렬되는 순서는 다음과 같다.

1) 2 뒤에 위치한 원소중 가장 작은 1과 2가 switch [ 1, 2, 7, 6, 3, 5 ]
2) 두번째 원소가 된 2보다 작은 건 없으니 pass [ 1, 2, 7, 6, 3, 5 ]
3) 세번째 원소 뒤 가장 작은 3과 7이 switch [ 1, 2, 3, 6, 7, 5 ]
4) 네번째 원소 뒤 가장 작은 5와 6이 switch [ 1, 2, 3, 5, 7, 6 ]
5) 다섯번째 원소 뒤 가장 작은 6과 7이 switch [ 1, 2, 3, 5, 6, 7 ]

자바 코드로 구현해보면 다음과 같다. 시간복잡도는 O(n²)

선택정렬

정렬 결과

삽입정렬 ( Insertion Sort )

삽입정렬은 이미 정렬된 부분을 비교하여 자신의 위치를 삽입하는 알고리즘.
예를 들어 [ 2, 1, 7, 6, 3, 5] 이라는 배열이 있다고 가정한다면

1) 삽입정렬은 두번째 부터 정렬을 시작하여 , 앞에 정렬된 원소들을 비교한다. 1가 타겟이 되며 , 2보다 작으므로 서로 switch
[ 1, 2, 7, 6, 3, 5]
2) 세번째 7의 경우, 주의할점은 앞의 정렬된 원소 [1, 2] 를 비교하는데 뒤의 원소부터 비교한다. 2는 7보다 작으니 pass, 1도 마찬가지므로 pass
[ 1, 2, 7, 6, 3, 5 ]
3) 네번째 6의 경우, 앞의 정렬된 원소 [1, 2, 7]를 비교하는데, 정렬된 원소 끝에서부터 비교. 7은 6보다 크니 switch [1,2,6,7] 순으로 변경. 1과 2는 6보다 작으므로 pass
4) 다섯번째 3의 경우, 앞의 정렬되 원소 [1, 2, 6, 7]을 비교하고, 정렬된 원소 끝에서부터 비교하면 , 7은 3보다 크므로 switch
[1, 2, 6, 3, 7] 이 되고 다음 6은 3보다 크므로 또 switch. [1, 2, 3, 6, 7] 순이 되며 , 1과 2는 3보다 작으므로 pass
5) 마지막 5의 경우도 위와 마찬가지로 정렬하게되어 [1, 2, 3, 5, 6, 7]로 return

자바 코드로 구현해보면 다음과 같다. 시간복잡도는 O(n²)

버블정렬 ( Bubble Sort )

버블정렬은 서로 인접한 두 원소를 검사하는 알고리즘이다. 위와 같이 [ 2, 1, 7, 6, 3, 5] 이라는 배열이 있다고 가정한다면
1-1) 첫번째 2와 두번째 1을 비교한다. 1이 2보다 크므로 switch [ 1, 2, 7, 6, 3, 5 ]
1-2) 두번째 2와 세번째 7을 비교한다. 2는 7보다 작으므로 pass [ 1, 2, 7, 6, 3, 5 ]
1-3) 세번째 7과 네번째 6을 비교한다. 7은 6보다 크므로 switch [ 1, 2, 6, 7, 3, 5 ]
1-4) 네번째 7과 다섯번째 3을 비교한다. 7은 3보다 크므로 switch [ 1, 2, 6, 3, 7, 5 ]
1-5) 다섯번째 7과 마지막 5를 비교한다. 7은 5보다 크므로 switch [1, 2, 6, 4, 5, 7]
-> 가장 큰 7이 제일 뒤에 위치한다.
2-1) 첫번째 1과 두번째 2를 비교한다. 1은 2보다 작으므로 pass [1, 2, 6, 4, 5, 7]
2-2) 두번째 2와 세번째 6을 비교한다. 2는 6보다 작으므로 pass [1, 2, 6, 4, 5, 7]
2-3) 세번째 6과 네번째 4를 비교한다. 6은 4보다 크므로 switch [1, 2, 4, 6, 5, 7]
2-4) 네번째 6과 다섯번째 5를 비교한다. 6은 5보다 크므로 switch [1, 2, 4, 5, 6, 7]
2-5) 다섯번째 6과 마지막 7을 비교한다. 6은 7보다 작으므로 pass [1, 2, 4, 5, 6, 7]
-> 두번째로 큰 6이 7앞에 위치한다.
(지금은 우연하게도 모두 순차적으로 정렬이 되었지만 나머지 앞에 1,2,4,5도 똑같이 정렬을 진행한다.)

자바 코드로 구현해보면 다음과 같다. 시간복잡도는 O(n²)

 

병합정렬 ( Merge Sort )

또는 합병정렬 , 이름에서 불러오는 것 같이 분할하여 다시 합병 또는 병합을 하여 정렬하는 알고리즘이다.
크게 3단계 나뉘어지는데
1. 원소들을 절반으로 분할하여 나눈다. (*나눈 원소들의 길이가 1이 될때까지) -> 분할
2. 나누어진 인접한 원소들끼리 정렬하여 합친다. -> 병합 or 합병

예를 들어 [ 2, 1, 7, 6, 3, 5] 이라는 배열이 있다고 또 가정한다면 1번 규칙에 의하여
1) [2,1,7] , [6,3,5] 로 나눈다.
2) [2,1] , [7] 그리고 [6,3] , [5] 로 나눈다. ( [2,1],[7] 한 묶음 그리고 [6,3], [5]가 한 묶음 )
3) [2] [1] [7] [6] [3] [5] 로 나누어진다.
4) 인접한 1,2를 정렬 [1,2] [7] 그리고 6과 3을 정렬 [3,6] [5] ( 2번 참고 )
5) 인접한 그룹끼리 또 정렬 [1,2,7] 그리고 [3,5,6]
6) 인접한 그룹끼리 또 정렬 [1,2,3,5,6,7]

합병정렬은 다른 정렬과 다르게 실제 정렬이 되도록하는 추가적 저장공간이 필요하며, 각 부분 그룹들이 정렬할때 역시 합병정렬이 이루어진다. ( 소스로 확인해보자. )

합병정렬은 binary tree로 형태로 쪼개어진다. 따라서 logN 의 시간복잡도를 가지며 n개의 합병을 진행할 수 있으므로 총 시간복잡도는 O(nlogN)이다.

 

퀵정렬

퀵정렬은 한 요소 (pivot)을 선택하여 해당 pivot을 기준으로 작으면 왼쪽 , 크면 오른쪽으로 옮겨진다. 그리고 피벗에 대하여 오른쪽과 왼쪽의 리스트를 재정렬한다. 이때 재정렬 역시 순환 호출하며 정렬을 반복하는 알고리즘이다.
퀵정렬 역시 크게 세단계로 나누어진다.
1. 피벗 기준으로 작은 수들은 왼쪽 , 큰 수들은 오른쪽으로 분할한다. -> 분할 (Divide)
2. 분할된 배열 또는 리스트를 정렬한다. 충분히 작아질 때까지 분할하여 ( 순환호출 ) 다시 정렬한다. -> 정복 (Conquer)
3. 순환 호출이 끝날때마다 합병 -> 결합(Combine)

예를 들어 [ 2, 1, 7, 6, 3, 5] 이라는 배열이 있다고 또 가정한다면 1번 규칙에 의하여 피벗을 선택.

1) 중간의 7를 pivot으로 정한다.
7보다 작은 수 -> 2, 1, 6, 3, 5
7보다 큰 수 -> 없음
[2, 1, 6, 3, 5] [7]

2) [2, 1, 6, 3, 5]에서 6을 pivot으로 정한다.
6보다 작은 수 -> [2,1,3,5]
6보다 큰 수 -> 없음
[2,1,3,5] [6] [7]

3) [2,1,3,5]에서 3을 pivot으로 정한다.
3보다 작은수 -> [2,1]
3보다 큰 수 -> [5]
[2,1] [3] [5] [6] [7]

4) [2,1] 에서 1을 pivot 으로 정한다.
1보다 작은 수 -> 없음
1보다 큰 수 -> [2]
[1] [2] [3] [5] [6] [7]

5) 합병 -> [1,2,3,5,6,7]

퀵정렬 역시 합병정렬과 마찬가지로 2쌍씩 반으로 쪼개어가며, n번의 순환호출이 나타날 수 있다. 따라서 시간복잡도는 O(nlogN)
하지만 리스트가 불균형하게 나누어지는 경우가 발생할 수도 있다. 이런 경우에는n번의 순환 호출이 2의 거듭제곱으로 발생되므로 최악의 경우 시간복잡도는 O(n^2)