티스토리 뷰

정렬 알고리즘 종류

정렬 종류

정렬 방법 

최고 효율 

평균 효율 

최악 효율 

특징 

버블 정렬 

 교환 방식 

n^2

n^2 

n^2 

구현하기 쉽다.

선택 정렬 

교환 방식

n^2

n^2 

n^2 

 

삽입 정렬

삽입 방식

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^1.5

n^2

삽입정렬을 보완한것으로 여러 개의 부분 리스트 생성 후 각각 삽입 정렬을 적용



버블 정렬

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

선택 정렬

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

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


삽입 정렬

두 번째 자료부터 시작하여 그 앞의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬
원소는 정해져있고 위치를 찾는다고 생각
  • 최선 : 이동없이 1번의 비교만이루어져 총 n-1번 비교 > O(n)
  • 최악 : 역순일 경우 > O(n^2)


병합 정렬

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

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



셸 정렬

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

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

댓글
댓글쓰기 폼