원소들을 특정 순서나 기준에 맞게 정렬하게끔 하는 알고리즘에는 다양한 방법이 있다.
Input 데이터로 <a1,a2,~~,an> 등 n개의 데이터가 주어지게 되면,
Output 데이터로 정렬 기준에 맞는 순열을 return 하게 된다.
이 정렬 알고리즘을 사용하게 되면 간편해지는 것들이 많은데
1) 특정 값을 리스트에서 검색하는 것이 빨라진다.
2) 최소/최대값 찾기에 용이해진다.
3) 중복값 찾기나 유니크한 값 찾기에 유용해진다.
4) 날짜별로 상태, 거래 등을 정렬하기 용이하다.
등등 다양한 장점들이 존재합니다..
그렇다면, 정렬 알고리즘에는 어떤 종류가 있는가
제가 들었던 수업에서는 크게 2가지 구분 방식이 있었습니다 .
1) 비교 정렬 vs 비 비교 정렬
비교 정렬 : 버블 정렬, 선택 정렬, 삽입 정렬 , 병합 정렬, 퀵 정렬, 힙 정렬
->정렬하는 데이터들 간의 비교 연산을 통해 정렬을 수행하는 알고리즘.
기본적으로 두 값을 비교하면서 더 작은 값이나 더 큰 값을 결정하여 정렬한다.
하지만 시간 복잡도 측면에서 최악의 경우 O(n^2) 또는 O(n log n)으로 최악의 경우 좋은 효율을 보이지 못함.
비 비교 정렬 -> 카운트 정렬 , 기수(Radix) 정렬
-> 두 값의 비교 없이, 데이터를 정렬한다.
두 값 간의 비교가 아닌 값의 범위나 특정 속성을 이용하여 정렬한다.
시간 복잡도가 O(n)으로 특정 조건 (데이터가 정수 or 범위가 작은 경우)에 매우 효율적이다.
2) 반복 vs 재귀
반복 정렬 : 버블 정렬, 선택 정렬, 삽입 정렬, 기수(Radix) 정렬
-> 반복문 (for 문)을 사용하여 데이터를 정렬하는 알고리즘이다. 데이터를 처리하는 동안
여러 번의 반복을 통해 정렬을 수행하며, 각 단계에서 요소들을 비교하고 교환하거나 이동시킨다.
반복에서 지정한 일정한 규칙에 따라 "점진적"으로 정렬을 수행함.
재귀 정렬 -> 퀵 정렬, 병합 정렬, 힙 정렬
-> 재귀 정렬은 재귀 함수를 사용하여 데이터를 정렬하는 알고리즘이다.
배열을 큰 덩어리에서 점점 작은 부분으로 나누고, 나눈 부분을 정렬한 후 다시 합치는(merge) 방식으로 동작한다.