정렬(Sorting)이란?

정렬(sort) 알고리즘이란 주어진 데이터가 있을 때 특정 규칙을 준수하도록 나열하는 문제이다.
특정 규칙을 준수하도록 나열한다는 의미는 특정 문제를 풀기위해 원하는(희망하는) 순서대로 다시 나열 한다는 것이다.


예를들어 주어진 데이터 A = { 4, 2, 1, 3 } 정수형으로 되어 있다고 가정해보자.
우리가 원하는 것은 A의 원소를 숫자가 커지는대로 또는 숫자가 작아지는대로 나열하고 싶다고 한다면
숫자가 커지는대로 정렬을 하면 A  = { 1, 2, 3, 4} 로 나열되고 숫자가 작아지는대로 정렬을 하면 
A  = { 4, 3, 2, 1}로 나열되는 것이다. 

정렬에서는  숫자가 증가하는 순을 오름차순정렬(Ascending Order Sorting) 이라고 하고
숫자가 작아지는 순서대로 정렬하는 것을  내림차순정렬(Descending Order Sorting)이라고 부른다.
일상생활에서는 숫자 말고도 문자 또는 문자열 순서대로 정렬할 필요가 있기도 하다.

즉, 오름찬순, 내림차순 정렬이 반드시 숫자의 개념에만 적용되는것은 아니다.
문자나 문자열 정렬시 알페벳순으로 정렬하기위 해서 a-z 와 A-Z의 아스키코드값을 비교하면서 알페벳 순이 큰 순서대로 정렬 될수도 있고 작은 순서대로 정렬될 수도 있을 것이다.

예를들어 NAMES = ["Alan Brooke", "George Marshall", "Frank Jack Fletcher", "Conrad Helfrich", "Albert Kesselring"] 가 있다면

NAMES 를 오름차순정렬을 한다면 알파벳순서대로 ["Alan Brooke", "Albert Kesselring",  "Conrad Helfrich",  "Frank Jack Fletcher", "George Marshall"] 처럼 될 것이고 내림차순 정렬을 한다면 그 반대가 되는 것이다.

정렬시 원하는 순서대로 나열하기위해서 하나이상의 규칙이 필요하기도하다.
예를들어 도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다.  
이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오에서 희망하는 정렬순서는 다음과 같다.

→ 국어 점수가 감소하는 순서로
→ 국어 점수가 같으면 영어 점수가 증가하는 순서로
→ 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
→ 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.)

위 문제를 풀려면 각 과목마다 점수를 비교하고 최종적으로 이름을 알파벳순으로 정렬해야 한다.
일반적으로 하나이상의 정렬 규칙이 요구되어지는 경우는 매우 흔한일이다.

 

Q. 정렬은 왜 필요할까 ?
정렬은 컴퓨터 분야에서 매우 중요한 알고리중 하나이고 프로그래밍을 전공하는 사람이라면 반드시 알아야 한다. 왜 이렇게 정렬이 중요할까? 정렬의 목적은 탐색과 검색을 용이하게 해준다. 
일상생활에서 정렬되어 있어서 검색이 용이한 사례는 전화번호 책(요즘은 공중전화가 없어서 거의 볼일이 없지만 예전애는 공중전화 부스마다 한권씩 배치 되어 있었다)과 영어사전(지금은 인터넷 사전들이 있어서 종이사전을 들고 다니는지 모르겠다)을 들 수. 있다. 

사전이 만약 알파벳순서로 정렬되어 있지 않다고 생각해보자? 아마 단어 하나 찾는것은 거의 운에 맡겨야 할 정도일 것이다.
컴퓨터 프로그래밍에서도 정렬은 일상생활 처럼 탐색, 검색을 위해  이진탐색(Binary Search) , 이진탐색트리(Binary Search Tree), 우선순위큐(Priority Queue), 힙(Heap) ,  최소신장트리(Minimum Spanning Tree)-크러스컬(Kruskal) 알고리즘, 자료저장을 위한 데이터베이스등 셀수 없이 많은 곳에서 사용된다.

그러다 보니 많은 많은 데이터를 빠르게 정렬하기위한 알고리즘 기법들이 연구되고 있고 지금까지 그 종류가 15종류(정확하지 않음)가 있다고 하는데 15가지모두 알수 없고 알고리즘 서적에서 가장 많이 언급되고 있는 정렬 알고리즘을 몇 가지만 살펴볼것이다.

 

1. 버블정렬(Bubble Sort)
2. 선택정렬(Selectio Sort)
3. 삽입정렬,(Insertion Sort) 
4. 쉘정렬(Shell Sort)
5. 쿽정렬(Quick Sort)
6. 합병정렬(Merge Sort)
7. 힙정렬(Heap Sort)  
8. 계수정렬(Counting Sort)
9. 기수정렬(Radix Sort)

 

정렬알고리즘을 하나씩 살펴보기 전에 정렬시 자주 사용되는 용어에 대해서 알 필요가 있다.

Q. stable sort vs unstable sort
정렬알고리즘에서 stable 하냐 unstable 하냐의 차이점은 정렬전 입력된 데이터의 원소중 동일합 값이 있을때 정렬후 그 순서가 유지되는냐 안되느냐의 차이이다.
예를들어 그림1을 보면 정렬되지 않은 리스트 원소중 중족되어 있는 값이 4이다. 
정렬전 하나는 A 위치에 있고 다른하나는 B 위치에 있다고 했을때 정렬후 stable sort 알고리즘을 사용하여 정렬을 한 경우 A가 B보다 앞에 있었다는 순서(order)는 유지되지만 unstable sort 알고리즘은 그 순서가 유지되지 않는다.

 

그림1. stable sort vs unstable sort

Bubble Sort, Insertion Sort, Merge Sort, Count Sort, Radix Sort등은 stable 하고  Quick Sort, Heap Sort unstable 하다. 

 

Q. Comparison sort vs Comparison sort ? 

comparison 하냐 안하냐의 차이는 정렬을 할때 원소의 데이터들을 서로 비교해가면서 정렬을 하면 comparison sort 라고 하고 그렇지 않으면 uncomparison sort 라고 부른다.
여기서 비교라는 것은 두 원소 a, b 가 있을때 a가 b보다 큰지 작은지 같은지(a > b , a < b, a == b)를 비교해가면서 정렬한다는 의미이다. 

Quicksort, Heapsort, Shellsort, Merge sort, Insertion sort, Selection sort Bubble sort 는 comparison sort 들이고 counting sort, radix sort는 uncomparison sort 이다.

 

Q. In place sort vs Out of place sort

정렬 알고리즘을 사용하다 보면 in-place or out of place라는 말이 나오는데
이는 정렬시 추가 공간(메모리)가 필요하냐 아니냐의 차이이다.
즉 입력된 데이터의 메모리만 조작해서 정렬이 가능한 경우를 in-place sort 라고 하고 
정렬 도중에 입력된 데이터 리스트외에 추가적인 메모리가 더 필요한경우를 out of place sort 라고 한다.

 

Q. internal sort vs external sort

ineternal sorting 은 데이터가 적어 메인메모리에 모두 저장하여 정렬이 가능한 정렬을 말한다.
하지만 external sorting 은 데이터가 너무 많아 메인 메모리의 용량을 초과한 경우 보조저장장치에 저장된 파일을 합병하여 원하는 하나의 정렬된 파일로 만드는 경우이다.
즉 하나의 파일을 여러개로 분할하여 내부 정렬(internal sort)을 한 다음 서브파일들로 저장한다.
그다음에 서브파일들을 하나씩 읽으면서 머지하여 하나의 정렬된 파일로 만드는 경우를 말한다.

[출처] https://studylib.net/doc/7439697/sort-algorithms

 

정렬알고리즘들을 비교한 표는 아래와 같다. 

algorithm	best	average	worst	in place	comparison	stable
버블정렬(Bubble Sort)				●	●
선택정렬(Selectio Sort)				●	●
삽입정렬,(Insertion Sort)				●	●
쉘정렬(Shell Sort)					●
쿽정렬(Quick Sort)					●
합병정렬(Merge Sort)					●
힙정렬(Heap Sort)					●
계수정렬(Counting Sort)					X	●
기수정렬(Radix Sort)					X	●
버킷정렬 (Bucket Sort)					△ (버킷 리스트를 정렬하기위한 sort에 의존적입)