[알고리즘] 정렬

난이도순 정렬

1.선택 정렬 O(n^2): 선형 탐색 반복

선형 탐색으로 최소값을 찾고 첫번째 위치에 놓으면 첫번째 가장 작은 요소가 확정된다. 반복.

2.삽입 정렬 O(n^2)/O(n): 2번째 요소부터 자신보다 작은 요소가 나올때까지 왼쪽으로 옮긴다. 반복. / 최대한 정렬되있을 때 빠르다

3.버블 정렬 O(n^2): 붙어 있는 2개의 거품 방울

끝에서부터 2개 요소를 비교해가며 다 작은 쪽을 왼쪽에 놓고 처음까지 오면 첫번째 가장 작은 요소가 확정된다. 반복.

4.병합 정렬 O(nlogn):1개가 될때까지 반으로 쪼개고 다시 합치면서 정렬한다.

5.퀵 정렬 O(nlogn)/O(n^2): 기준 요소를 구하고 양쪽 끝에서부터 기준 요소보다 크거나 작은 요소를 찾으면 멈추고 찾은 요소 2개의 위치를 바꾼다. 좌우 요소가 만나면 기준 요소와 바꾼다. 기준 요소를 기준으로 2개 배열로 나눠 반복. / 최대한 정렬되있을 때 느리다

*힙 정렬 O(nlogn): 빈 힙에 요소들을 순서대로 넣고 하나씩 꺼낸다.

 

- 일반 정렬: 비교(<,>,=)로 정렬

- 특수 정렬: 다른 방법으로 정렬. 더 빠르다.

1.Counting 정렬 O(n+k): 별도의 Counting 배열을 만들어 배열[값] = 1 또는 배열[값] += 1로 특정 값의 개수를 세는 정렬

2.버켓 정렬 O(n+k): k(최대 요소값)개의 큐(버켓)를 만들어 Counting 정렬과 비슷하게 큐[값]에 값을 넣는다(다른 점은 Couting 정렬처럼 수를 세는게 아니라 큐에 여러개를 넣는 것). 그 다음 큐들을 순서대로 비운다(들어간 요소를 꺼낸다)

3.기수 정렬 O(D(n+B)): 긴 수가 주어졌을 때 1,10,100,...의 자리수 순서대로 정렬