정렬

안녕하세요 : ) 오늘은 정렬에 대해 알아볼게요

 

정렬은 다수의 자료를 특정 기준에 의해 작은 값부터 큰 값(ascending) 또는 그 반대의 순서(descending)로 재배열하는 것이다.

정렬의 예는 다음과 같다.

버블정렬(Bubble Sort), 카운팅정렬(Counting Sort), 선택정렬(Selection Sort), 퀵정렬(Quick Sort), 삽입정렬(Insertion Sort), 병합정렬(Merge Sort)가 있다.

이 정렬알고리즘들을 비교하기 위해 간단하게 표로 나타내겠다.

 

알고리즘	평균수행시간	최악수행시간	기법	비고
버블정렬	O(n^2)	O(n^2)	비교와 교환	코딩이 가장 쉬움.
카운팅정렬	O(n+k)	O(n+k)	비교환	n이 비교적 작을때만 가능.
선택정렬	O(n^2)	O(n^2)	비교와 교환	교환의 횟수가 버블, 삽입보다 작음.
퀵정렬	O(nlogn)	O(n^2)	분할정복	최악의 경우O(n^2)이지만 평균적으로 가장 빠름.
삽입정렬	O(n^2)	O(n^2)	비교와 교환	n의 개수가 작을 때 효과적임.
병합정렬	O(nlogn)	O(nlogn)	분할정복	연결리스트의 경우 가장 효율적인 방식.

 

• 안정 정렬(Stabale Sort) : 중복된 값은 입력 순서와 동일하게 정렬. 삽입정렬, 병합정렬, 버블정렬
• 불안정 정렬(Unstable Sort) : 안정 정렬과 반대. 퀵 정렬, 선택정렬

 

파이썬의 정렬은 안정 정렬, 자바는 불안정 정렬

public static <T> void sort(T[] a,
                            int fromIndex,
                            int toIndex,
                            Comparator<? super T> c)

자바의 안정 정렬

 

 

참고👇

https://hongl.tistory.com/9

안정 정렬 vs 불안정 정렬