[알고리즘] 정렬알고리즘 _ 버블, 선택, 삽입, 병합, 셸

정렬 알고리즘 종류

정렬 종류	정렬 방법	최고 효율	평균 효율	최악 효율	특징
버블 정렬	교환 방식	n^2	n^2	n^2	구현하기 쉽다.
선택 정렬	교환 방식	n^2	n^2	n^2
삽입 정렬	삽입 방식	n	n^2	n^2	코드가 간단하고 n의 수가 작을 때 유리하다.
병합 정렬	병합 방식	n x log(n)	n x log(n)	n x log(n)	입력자료를 분할하여 병합하므로 별도의 기억장소가 필요하다.
퀵 정렬	나누기(부분집합) 방식	n x log(n)	n x log(n)	n^2	분할한 입력자료를 재귀적으로 반복하여 정렬하므로 빠르다.
힙 정렬	선택 방식	n x log(n)	n x log(n)	n x log(n)	입력자료를 힙이라는 자료형을 유지하도록 선택하여 정렬한다.
셸 정렬	삽입 방식	n	n^1.5	n^2	삽입정렬을 보완한것으로 여러 개의 부분 리스트 생성 후 각각 삽입 정렬을 적용

버블 정렬

인접한 원소를 검사하여 ( 1↔2, 2↔3, 3↔4 , ... , n-1↔n ) 1회전이 끝나면 제일 큰 값이 맨 뒤로 이동하게 된다.

선택 정렬

가장 큰 원소를 찾아 맨 마지막 값의 자리와 변경하는 정렬 ( 혹은 가장 작은 원소를 찾아 맨 앞의 자리와 변경 )

위치는 정해져있고 원소를 찾는다고 생각

삽입 정렬

두 번째 자료부터 시작하여 그 앞의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬

원소는 정해져있고 위치를 찾는다고 생각

• 최선 : 이동없이 1번의 비교만이루어져 총 n-1번 비교 > O(n)
• 최악 : 역순일 경우 > O(n^2)

병합 정렬

- 분할 : 배열을 같은 크기의 2개의 부분 배열로 분할

- 정복 & 결합 : 부분배열을 정렬해서 하나의 배열에 합병

셸 정렬

- 삽입정렬을 보완한 알고리즘

- 연속적이지 않은 여러 개의 부분 리스트를 생성하여 각 부분 리스트를 삽입 정렬을 이용하여 정렬