한 번에 정리하는 정렬 알고리즘

이번 포스팅은 c++, Java, Python 등 프로그래밍 및 자료구조, 이산수학, 화일처리 등에서 배우는 정렬 알고리즘에 대해 다룰 것이다. 항상 정렬 알고리즘을 배우고, 직접 구현을 해도 항상 머리속에 남질 않는다. 코드로 아무리 봐도 머리속에 남지 않는 경우가 많아, 시각적인 애니메이션과 함께 설명을 하려 한다. 정렬 알고리즘은 한 번 정도는 확실하게 익히고 갈 필요성이 있다.

 

많은 정렬 알고리즘들이 존재하지만 이번 포스팅에선 가장 기본적인 5가지 정렬 알고리즘에 대해서 다룰 것이다.

1. merge sort (합병 정렬)
2. insertion sort (삽입 정렬)
3. selection sort (선택 정렬)
4. bubble sort (버블 정렬)
5. quick sort (퀵 정렬)

1. merge sort (합병 정렬)

분할정복을 이용한다. 어려운 용어가 아니다. 데이터가 담겨있는 배열을 각각이 크기가 1이 될때까지 분할 하고, 작은 것을 앞, 큰 것을 뒤에 붙여 다시 원래의 길이로 합쳐가는 과정이다. 해당 알고리즘은 그림으로 보는 것이 편할 것 같다.

쉽게 말해, 배열을 반으로 쪼개고, 1개로 쪼개지면 쪼개지기 이전 단계의 다른 쪼개진 배열 조각과 정렬해 윈래의 길이로 합쳐가는 과정이다. 

 

2. insertion sort (삽입 정렬)

삽입 정렬은 배열의 앞부터 탐색하면서 가장 작은 값 순서로 해당 값을 삽입하는 방식이다.

 

3. selection sort (선택 정렬)

선택정렬은 인덱스(지금 배열에서 어디를 보고 있는지)를 하나씩 증가시켜가며 남은 배열 중 가장 작은 값과 현재 인덱를 바꿔주는 정렬이다.

 

 

4. bubble sort (버블 정렬)

버블 정렬은 배열의 시작 부터 인덱스(지금 배열에서 보고 있는 위치)의 값과 바로 다음 인덱스의 값과 비교해 앞의 값이 뒤의 값보다 큰 경우면(정렬이 되지 않은 경우면) 두 위치를 바꾸는 정렬이다. 이 정렬 방법은 가장 큰 값부터 순서대로 맨 뒤로 보내는 방식이다.

 

 

5. quick sort (퀵 정렬)

분할정복, pivot, left, right을 사용하는 정렬이라고 볼 수 있다.

 

기준을 정하여 배열을 분할하고, 분할된 배열들을 정렬하고, 다시 붙이는(정복) 방식의 정렬이다.

 

배열 가장 왼쪽을 pivot 을 지정하고 위치상 pivot 보다 뒤에 위치한 배열값들 중, pivot 바로 뒤의 값부터 pivot에서 먼 쪽으로 가면서 pivot 보다 작은 위치(몇 번째의 값인지 숫자)를 left, 가장 오른쪽 끝에서 pivot 쪽으로 오면서 pivot 보다 값이 작은 위치를 right 라고 할 것이다.

 

1. pivot 뒤의 배열중 가장 왼쪽 부터 확인하여 pivot 보다 작은 값으로 left 를 정한다.(left가 존재하지 않는다면 더 이상 보지 않아도 된다.)

 

2. left가 설정 되었다면 pivot 뒤의 값들 중 가장 오른쪽 부터 확인하여(left 보다 뒤의 값 중) pivot 보다 값이 작은 위치를 right 로 지정(동일하게 right 가 존재하지 않는다면 더 이상 보지 않아도 됨.)

 

3. left 와 right 모두 존재한다면 두 값을 바꾼다. 두 위치의 값을 바꿔준 후 left 를 더 뒤로 가며 다음 left를 찾는다. -> 1,2를 반복.

 

값을 바꾼 후 left를 한 칸 옮기려 할 때에 right와 같은 위치가 되려 한다면 left의 값과 pivot의 값을 교환한다.

 

1~3 의 정렬 한 번이 끝났다면 pivot은 자신의 위치를 찾은 것이다. 그럼 이 자리를 잡은 pivot을 기준으로 왼쪽, 오른쪽으로 분리하여 각각에서 1~3을 반복하며 위치를 하나씩 잡아준다. -> 분할정복

 

해당 과정을 재귀적으로 실행하여 정렬을 하는 것이 퀵정렬 이다.

 

 

정렬의 시간 복잡도 / 공간 복잡도