Sort
정렬에 대한 간단한 정리
정렬이란 순서대로 나열한 것이다. 정렬방식은 오름차순 내림차순이 있다.
정렬 알고리즘
선택정렬 삽입정렬 버블정렬 퀵 정렬
정렬 알고리즘의 성능 지표
빅 오 < 빅 세타 < 빅 오메가
빅 오
최고 차항의 개수가 n^2을 넘지 않는 모든 함수의 집합
빅 세타
최고 차항의 개수가 n^2인 모든 함수의 집합
빅 오메가
최고 차항의 개수가 n^2작지 않은 모든 함수의 집합
Θ(n^2)
선택 정렬
선택정렬은 가장 큰 원소를 찾아 맨 끝자리 원소와 자리를 바꾸는 것이다.
선택 정렬의 특징 :
수행시간이 항상 O(N^2)이다.
버블 정렬
버블 정렬은 두 원소를 비교하여 더 큰원소를 오른쪽으로 자리를 교환하는것이다.
삽입 정렬
정렬된 리스트와 정렬되지 않은 리스트를 분리하고 정렬되지 않은 리스트에 있는 하나의 원소를 정렬된 리스트에 삽입하여 정렬하는것
삽입 정렬의 특징 :
삽입정렬은 입력에 민감하다.
정렬된 경우 O(N)
입력이 역으로 정렬된 경우 O(N^2)
입력이 거의 정렬된 경우 최고의 성능
입력크기가 작은경우도 최고의 성능
합병정렬이나 퀵정렬과 함께 사용됨
Θ(nlogn)
병합 정렬
입력을 반으로 나누어 전반부와 후반부를 각각 정렬하고 정렬된 부분을 병합하여 정렬하는것
퀵 정렬
기준 원소를 하나 잡아 기준 원소보다 작은 원소와 큰 원소 그룹으로 나누어 각각 정렬하는 것
쉘 정렬
삽입정렬을 이용하여 작은 값을 가진 원소는 리스트의 앞쪽으로 큰 값을 가진 원소는 리스트의 뒤쪽에 배치하는 과정을 반복하여 정렬하는것
폐쇄