[정렬-JAVA] 0. 들어가는 말

 

---

1. 알고리즘에서 정렬이란

   지금까지 풀었던 코딩 문제들은 알고리즘이라기 보다는 구현 문제에 가까웠던 것 같다. 알고리즘이 적용된 문제들도 기초 알고리즘이 적용되었지, BFS(뭔지 모름)라던가.. 깊이 탐색이라던가.. 하는 내용들이 쓰이진 않았던 것 같다. 이런 내용들에 아예 무지해서 썼는데도 모르는 걸 수 도 있다.

   아무튼 지금까지 많은 200문제 가량 풀어보았는데, 정렬을 요구하는 문제 상황들이 꽤 있었다. 데이터를 특정 기준으로 정렬했을 때 얻을 수 있는 이점이 무엇이 있을까 생각해보았다. 의외로 이런 상황이 많더라. 출석부는 보통 '가나다라' 순서대로 정렬되어있다. 사원의 급여 표를 정리할 때는 오름차순이든 내림차순이든 정리해두는 편이 깔끔하다. 블로글에 게시글을 올린다고 할 때 오름차순으로 정렬해둔다. 그러니까, 일련의 데이터에서 한 눈에 알아볼 수 있는 아주 직관적인 규칙성 중 하나가 정렬이고, 이것은 생산성이 향상될 수 있도록 도울 수 있기 때문에 자주 쓰이고, 수요에 맞춰 여러 종류의 알고리즘이 등장한 것이다. 라고 생각해보았다.

무엇을 먼저 보이게 할 것인가?

2. 대표적인 정렬 알고리즘의 종류

   숫자든 문자든 정렬을 한다고 하면 가장 먼저 떠올리는 것은 '오름차순' '내림차순' 일 것이다. 이건 코드를 조금만 바꿔주면 언제든지 수정이 가능하다. 대표적인 정렬 방식의 종류는 다음과 같다.

1. 버블 정렬 (Bubble Sort)
2. 선택 정렬 (Select Sort)
3. 계수 정렬 (Counting Sort)
4. 삽입 정렬 (Insertion Sort)
5. 병합 정렬 (Merge Sort)
6. 퀵 정렬 (Quick Sort)
7. 기타 등등

위 6가지 정렬 이 외에도 정말 다양하게도 많다. 사실 줄기적인 부분을 이야기하는거지, 사람에 따라서 얼마든지 변형하여 활용할 수 있기 때문에 정확한 가짓수는 알 수 없다. 하지만 위 내용들은 간단하면서도 기초적인 알고리즘인지라, 알아둬서 손해볼 건 없는게 아니라 알아둬야 하는 내용이다.

 

3. 정렬 알고리즘의 특성 정리

정렬	시간 복잡도		공간 복잡도
	최고	최악
버블 정렬	O(N2)	O(N2)	O(N2)
선택 정렬	O(N2)	O(N2)	O(N2)
계수 정렬	O(N+K)	O(N+K)	O(K)
삽입 정렬	O(N)	O(N2)	O(N2)
병합 정렬	O(N LogN)	O(N LogN)	O(N LogN)
퀵 정렬	O(N LogN)	O(N2)	O(N LogN)

   직관적으로 생각하면 된다. O( * )에서 *에 해당하는 값이 작을수록 성능이 좋다는 뜻이다. 복잡함이 작다는 뜻이니까! 특별히 계수 정렬에서 K의 값이 무엇인지 궁금할 수 있는데, 이것은 정렬하고자 하는 데이터의 최댓값을 의미한다. 예를들어 {1, 3, 2, 5, 4, 0, 8, 9, 1000, 10 } 이라는 데이터가 있다면 K는 데이터 내 최댓값 1000이다. 

 

4. 어떤 정렬 알고리즘을 사용해야 하는가?

   '좋은 알고리즘'을 판별하는 몇 가지 기준이 있다. 쉽게 말하면 연산 속도가 빠를수록 좋고, 사용되는 메모리가 적을수록 좋다. 연산 속도를 시간 복잡도라 하고 빅-오 표기법으로 표현한다. 연산에 요구되는 메모리의 정도는 공간 복잡도로 표현한다. 즉 시간 복잡도가 적을수록, 공간 복잡도가 적을수록 좋다고 할 수 있는 것으로 보인다.

   모든 종류의 정렬 알고리즘은 괜히 탄생한게 아니다. 상황에 맞게 사용하면 된다. 버블 정렬과 선택 정렬은 구현이 매우 간단하여 메모리와 시간이 충분하다면 그냥 이걸 쓰면 된다. 처음 정렬 알고리즘을 배울 때 애용했던 정렬법이다. 구조도 직관적이라서 정렬 알고리즘을 배우지 않은 사람이 본능적으로 사용한 알고리즘일 수 있다. 내가 그랬다.

쓰고 보니 버블 정렬

   앞으로의 포스팅에 각 정렬별 특성과 알고리즘을 구현한 코드와 설명을 올릴 계획이다. 개인적으로 공부 내용을 정리하는데 목적이 있기도 하지만, 나눔의 목적도 있으므로 혹시라도 잘못된 정보가 있다면 편하게 댓글에 남겨주시면 좋을 것 같습니다.

 

5. 눈으로 보는 정렬 알고리즘

아래 링크를 타고 들어가서 보고자 하는 정렬 알고리즘을 클릭하면 된다. 어떤 방식으로 정렬이 일어나는지 알 수 없다면 참고해보는 것도 좋을 것 같다.

 

https://www.toptal.com/developers/sorting-algorithmsㅇ

Sorting Algorithms Animations