정렬,버블,선택,삽입,힙,병합,퀵,Sort,Bubble,Selection,Insert,Heap,Merge,Quick

버블정렬

- 배열의 앞뒤 요소를 비교해가면서 가장 큰 값을 배열의 맨뒤로 보내는 방식

- O(n^2)

 

선택정렬

- 배열을 순회 하면서 가장 찾은 값을 찾아서 맨 앞에 위치와 바꾸는 방색

- 버블 정렬과 달리 매번 값을 바꾸는게 아닌 가장 찾은 값 인덱스를 찾고 한번만 swap이 일어난다.

- O(n^2)

 

삽입정렬

- 새로운 배열에 선택된 값을 정렬된 위치에 넣는 방식으로 정렬이된다.

- 기존에 데이터가 정렬된 상태라면 조금 더 유리하다.

- O(n^)

 

힙

- 힙트리를 이용한 정렬

- O(NlogN)

 

병합

- 분할, 정복, 결합

- 개념이 중요함

- 멀티스레드에서 분할해서 정복하고 같이 결합하는 방식 등으로 활용될 수도 있는 개념이다.

- O(NlogN)

 

퀵

- 최악 O(N^)

- 평균 O(NlogN)

- 병합은 임시 벡터를 만들기 때문에 퀵정렬이 평균적으로 더 빠를 수 있다.