🔣 기본적인 정렬 알고리즘
정렬 알고리즘에는 여러가지가 있겠지만 우선 기본적인 수준에서의 알고리즘을 먼저 알아보고자 한다.
☑️선택 정렬 (Selection Sort)
가장 생각해내기 쉬운 정렬이다. 하나씩 쌓아간다는 방식이다.
전체 n개의 수에서 max/min 값을 찾아서 첫 번째 인덱스에 넣고
그 다음 n-1개의 수에서 max/min 값을 찾아서 두 번째 인덱스에 넣고 이 과정을 반복한다
마지막 2개의 숫자를 탐색하고 나면 정렬이 끝나 있다. max/min 에 따라서 최대/최소 선택 정렬 이라고 한다
시간 복잡도는 무조건 n+n+1...2 번 탐색 하므로 ==> O(n^2)
공간 복잡도는 index n개의 배열만 있으면 되므로 O(n) 이다
☑️삽입 정렬 (Insertion Sort)
이름 그대로 배열에서 새로운 수가 삽입될 공간을 찾아 끼워 넣는 방식이다.
전체 n개의 수에서 두 번째 인덱스부터 그 전 인덱스와 값을 비교한다.
값이 작다면 swap 하는 과정을 더 이상 값이 작지 않을 때 까지 반복한다
마지막 1개의 숫자까지 삽입을 마치면 정렬이 끝나 있다.
시간 복잡도는 최악의 경우 매 삽입마다 내 앞에 있는 모든 인덱스의 숫자를 비교해야하는 경우이므로
1+2+3+...n-1 ==> O(n^2)
최고의 경우는 이미 정렬이 마쳐있어서 한 번만 비교하면 되는 경우
1+1+... 1 ==> O(n)
다만 Big-O notation 에서는 최악의 경우를 기준으로 평가해야하므로 시간 복잡도는 O(n^2) 이 된다.
공간 복잡도는 index n개의 배열만 있으면 되므로 O(n) 이다
☑️버블 정렬 (Bubble Sort)
한번에 두 개의 숫자를 이동하고 한번 수행시에 한개의 max/min 값이 결정난다는 점에서
선택정렬과 한번 수행시의 결과는 같지만 최대 최솟값을 만나기 전까지의 숫자들이 어느정도 정렬이 된다는 점에서 차이가 있다
1,2번 인덱스를 비교한다 -> 1번이 크면 2번과 swap 한다 -> 2,3번 인덱스를 비교한다... 반복
시간 복잡도는 탐색 수는 n-1 + n-2 + ... 1 이므로 ==> O(n^2)
공간 복잡도는 index n개의 배열만 있으면 되므로 O(n) 이다
☑️합병 정렬 (Merge Sort)
여기서 부터는 Divide and Conquer 전략이 적극적으로 사용된다.
정렬에서의 Divide and Conquer 전략은 데이터 배열을 반으로 쪼개 나간다는 점에서 공통점이 있다.
Merge Sort 에서는 반으로 쪼개다 데이터가 1개 남으면 쪼개진 데이터와 합병해나가는데
합병해 나가면서 크기를 비교해 새로운 배열에 넣는다.
1 1 1 1 -> 2 2 -> 4 인데 각 단계별로 4번씩 비교한다(두 개의 데이터를 비교해 하나를 새 배열에 집어넣음)
분할 하는 과정은 log_n 번
즉 log_n 번 나누고 각 단계마다 n번 탐색하니 시간 복잡도는 O(nlog_n) 이 된다
공간 복잡도는 index n개의 배열과 새로운 데이터를 넣을 배열 하나가 더 필요하므로 O(2n)이다
☑️퀵 정렬 (Quick Sort)
피벗을 기준으로 큰 수는 우측으로 작은 수는 좌측으로 보내는 방법을 사용한다.
세부 로직은 배열 좌, 우측을 탐색하는 변수를 두고, 서로 다른 방향으로 진행하며 각각 작은/큰 수가 나올 때 까지 인덱스를 증가시킨다.
둘 다 적절한 수를 찾고나서 left<right 이면 두 인덱스의 배열값을 교환하고 Divide 한다
Merge Sort과 같은 Divide and Conquer 전략을 사용하지만 Divide 과정에서 차이를 보인다
Merge Sort 는 Divide 과정이 언제나 n/2 로 일정하게 쪼개지만, Quick sort는 pivot 을 기준으로 좌, 우측으로 배열을 쪼갠다.
따라서 Quick sort 는 최악의 경우에는 언제나 한쪽 방향으로만 쪼개지므로 깊이가 n이 나오고, 최적일 때는 항상 피벗이 중앙에 위치하는 경우로 log_n 이 나온다.
최악의 경우 때문에 Merge Sort 보다 비효율적으로 보이지만 최악의 경우는 자연스러운 상태에서는 잘 나오지 않으며, 일반적
으로 Quick Sort 가 Merge Sort 보다 20%정도 성능이 더 좋다고 알려져있다.
