선택 정렬
최솟값을 찾아 자리를 바꿔나가는 것
최악의 경우 시간복잡도가 O(n**2)
최솟값 찾기 n 번 + 비교 1 + 2+ 3+ .... + n-1 번 = (n2+n)/2 → O(n2)
버블 정렬
최악의 경우 시간복잡도가 O(n**2)
앞뒤를 비교하면서 작은 것은 앞, 큰 것은 뒤로 자리를 바꿈
퀵 정렬(빨라서)
이론상으로는 시간복잡도가 O(N*logN)
💡 그러나 최악의 경우, 예를 들어 87654321 이라면 O(N**2) 이므로, 이를 보완하기 위해 퀵소트는 기준점(피봇)을 랜덤하게 잡거나, 중앙지점을 잡도록 구현되어있다. 경우에 따라 시간복잡도가 달라질 수 있기 때문에 unstable하다고 한다.31285764 → 3보다 작은 것은 3 왼쪽, 3보다 큰 것은 3 오른쪽
12385764 → 3의 위치는 고정! 2보다 작은 것은 2 왼쪽, 큰것은 2 오른쪽이므로 현 위치 고정
12385764 → 8보다 작은 것은 왼쪽, 큰것은 오른쪽
12357648 → 8의 위치는 고정! 5보다 작은 것은 왼쪽, 큰것은 오른쪽
12345768 → 5의 위치는 고정, 4보다 작은 것은 왼쪽, 큰것은 오른쪽
12345768 → 4의 위치는 고정, 7보다 작은 것은 왼쪽, 큰것은 오른쪽
12345678 → 6에 대해서 비교해봐도 결과는 같음. 정렬 완성!
병합 정렬 - 합치는 정렬
어떤 경우에도 시간복잡도가 O(NlogN) 이다.
장점: 안정적이다
단점: 배열을 새로 만들어야 하므로 메모리를 많이 할당해야 한다.
메모리가 넉넉하면서 안정적인 알고리즘을 사용하고 싶을 때 사용한다.
32814576 → 반씩 나눈다
3281 4576 → 반씩 나눈다
32 81 45 76 → 반씩 나눈다
3 2 8 1 4 5 7 6 → 두개씩 정렬을 시작한다.
23 18 45 67 → 두 블럭씩 정렬, 2pointer 개념 사용
1238 4567
12345678
Radix 정렬
수의 범위가 짧을 때, 메모리가 넘쳐날때 사용
n자리의 빈 배열을 만들어 두고, 수열을 돌면서 해당 숫자가 있으면 배열에 1을 추가한다.
배열을 돌면서 1이 있는 인덱스를 쭉 출력한다.
