정렬
- Comparison-based sorting : 데이터의 크기를 비교(일반적인 정렬)
알고리즘 특성
- stable : 크기가 같은 데이터를 정렬할때 입력 순서를 유지 해줌
- in-Place : 입력 데이터 외에 다른 데이터가 필요 하지 않은 것(입력 데이터의 크기와 무관하게 필요한)
Bubble Sort
-
-
한번의 pass마다 가장 큰 숫자가 제일 오른쪽에 위치함
-
-
플래그로 발전 시킬 수 있음
-
마지막으로 교환한 위치를 저장하고 다음 패스에서 저장한 위치까지만 실행
-
rabbit and turtle data
- 왼쪽의 큰 데이터만 오른쪽으로 옮기기 때문에 오른쪽의 작은 데이터는 느리게 왼쪽으로 이동함
Cocktail Shaker Sort
- bubble sort의 단점(토끼와 거북이 데이터)을 개선
- bubble sort의 각 pass를 한번은 왼쪽에서 오른쪽 그 다음은 오른쪽에서 왼쪽으로 실행
Comb Sort
- bubble sort에서 거북이 데이터를 줄이고자 함
- bubble sort에서는 인접한 두 데이터를 비교
- 비교하는 두 데이터 사이의 거리를 gap이라고 함
- bubble sort의 gap = 1
- Comb sort에서는 gap의 크기를 1보다 크게
- bubble sort의 pass가 진행됨에 따라 gap의 크기를 줄임
- gap의 크기(k는 1.3을 권장)
- in-place
- Not Stable : gap 때문에 생김
Selection Sort
- 정렬 중간에 데이터가 2개로 나뉘어 짐
- 왼쪽 : 정렬이 된 데이터
- 오른쪽 : 정렬이 되지 않은 데이터
- 오른쪽 데이터의 제일 작은 데이터를 뽑아서 오른쪽 데이터의 제일 앞 숫자와 교환
- in-place
- Not stable : swap에서 제일 앞에 있는 것과 순서를 바꾸기 때문에
Insertion Sort
- 정렬 중간에 데이터를 2개로 나눔(selection과 동일)
- 왼쪽 : 정렬이 된 데이터
- 오른쪽 : 정렬이 되지 않은 데이터
- 오른쪽 제일 앞 숫자를 왼쪽의 알맞은 위치에 삽입, 삽입할 위치의 오른쪽 데이터를 한칸씩 밈
- Inserting 과정
- 1pass 과정 왼쪽 하나씩 비교함
- 전체 과정
- in-place
- Stable : 똑같은 숫자가 인접할때 같은경우 교체를 안함
Shell Sort
- Insertion sort를 기본으로 함
- gap을 사용
- gap이 1이 되면 insertion sort와 동일
- gap이 N이라는 의미 :
- N만큼 떨어진 노란색 데이터 끼리만 insertion sort를 실행
- 1,6,11,16번째 실행
- 2,7,12,17번쨰 끼리 실행
- n이 5개면 서브 시퀀스가 5번이 되는 것
- 색깔별로 insert하는게 아니라 그냥 gap만큼 띄어진 곳에서 시작해서 하나씩 insert하는 방식으로 코드를 짬
- count할때 &&에서 앞에가 false면 뒤의 연산자의 횟수는 카운트 x
KMU SW