| 선택 | 첫칸부터 데이터들 중에 제일 작은 데이터를 찾아서 채우는 방식으로 정렬하는 알고리즘 |
0회전 59 34 80 27 61 90 55 37 25 43
1회전 25 34 80 27 61 90 55 37 59 43
2회전 25 27 80 34 61 90 55 37 59 43
3회전 25 27 34 80 61 90 55 37 59 43
4회전 25 27 34 37 61 90 55 80 59 43
5회전 25 27 34 37 43 90 55 80 59 61
6회전 25 27 34 37 43 55 90 80 59 61
7회전 25 27 34 37 43 55 59 80 90 61
8회전 25 27 34 37 43 55 59 61 90 80
9회전 25 27 34 37 43 55 59 61 80 90| 거품 | 서로 인접한 데이터끼리 비교해서 정렬하는 알고리즘 |
0회전 59 34 80 27 61 90 55 37 25 43
1회전 34 59 27 61 80 55 37 25 43 90
2회전 34 27 59 61 55 37 25 43 80 90
3회전 27 34 59 55 37 25 43 61 80 90
4회전 27 34 55 37 25 43 59 61 80 90
5회전 27 34 37 25 43 55 59 61 80 90
6회전 27 34 25 37 43 55 59 61 80 90
7회전 27 25 34 37 43 55 59 61 80 90
8회전 25 27 34 37 43 55 59 61 80 90
9회전 25 27 34 37 43 55 59 61 80 90| 삽입 | 두번째 데이터부터 앞에 있는 데이터들 사이 적절한 곳에 삽입하면서 정렬하는 알고리즘 |
0회전 59 34 80 27 61 90 55 37 25 43
1회전 34 59 80 27 61 90 55 37 25 43
2회전 34 59 80 27 61 90 55 37 25 43
3회전 27 34 59 80 61 90 55 37 25 43
4회전 27 34 59 61 80 90 55 37 25 43
5회전 27 34 59 61 80 90 55 37 25 43
6회전 27 34 55 59 61 80 90 37 25 43
7회전 27 34 37 55 59 61 80 90 25 43
8회전 25 27 34 37 55 59 61 80 90 43
9회전 25 27 34 37 43 55 59 61 80 90| 쉘 | 정렬해야할 데이터의 간격을 이용해서 정렬하는 방식 |
| 각각의 리스트를 정렬할 때는 삽입 정렬 | |
| 각 회전마다 간격을 수정하는데 간격을 밤으로 줄일 때 짝수가 나오면 +1을 해서 홀수로 만듦 |
정렬할 데이터 수 : 10개
간격의 초깃값 : 10 / 2 = 5
0회전 59 34 80 27 61 90 55 37 25 43
59 90
34 55
80 37
27 25
61 43
59 90
34 55
80 37
27 25
61 43
59 90
34 55
37 80
25 27
43 61
59 34 37 25 43 90 55 80 27 61
1회전 59 34 37 25 43 90 55 80 27 61
간격값 수정 : 5 / 2 + 1 = 3
59 25 55 61
34 43 80
37 90 27
59 25 55 61
34 43 80
37 90 27
25 55 59 61
34 43 80
27 37 90
2회전 25 34 27 55 43 37 59 80 90 61
간격값 수정 : 3 / 2 = 1
25 34 27 55 43 37 59 80 90 61
| 퀵 | 첫번째 값을 피봇( pivot )으로 설정 |
| 피봇을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 애들을 정렬 |
|
| low와 high를 이용해서 정렬 | |
| low는 왼쪽에서 오른쪽으로 탐색해가다가 피벗보다 큰 데이터를 찾으면 멈춤 |
|
| high는 오른쪽에서 왼쪽으로 탐색해가다가 피벗보다 작은 데이터를 찾으면 멈춤 |
|
| low와 high 교체 | |
| low와 high가 엇갈릴 때까지 반복 | |
| 엇갈려서 멈추면 high와 피봇을 교체 | |
| 다음 반복에서 피봇을 기준으로 왼쪽 오른쪽 리스트에서 위 과정 반복 |
0회전 59 34 80 27 61 90 55 37 25 43
L H
59 34 43 27 61 90 55 37 25 80
L H
59 34 43 27 25 90 55 37 61 80
L H
59 34 43 27 25 90 55 37 61 80
L H
59 34 43 27 25 37 55 90 61 80
H L
55 34 43 27 25 37 59 90 61 80
피봇이랑 교체
1회전 55 34 43 27 25 37 59 90 61 80
55 34 43 27 25 37
P
55 34 43 27 25 37
H L
37 34 43 27 25 55
피봇이랑 교체
90 61 80
P H L
80 61 90
피봇이랑 교체
2회전 37 34 43 27 25 55 59 80 61 90
P P
37 34 43 27 25
L H
37 34 25 27 43
L H
37 34 25 27 43
H L
27 34 25 37 43
피봇이랑 교체
80 61
H L
61 80
피봇이랑 교체
3회전 27 34 25 37 43 55 59 61 80 90
P
27 34 25
L H
27 25 34
L H
27 25 34
H L
25 27 34
피봇이랑 교체
4회전 25 27 34 37 43 55 59 61 80 90
| 힙 | 힙 트리를 이용해서 정렬하는 방식 |
| 오름차순으로 정렬하려면 최소힙 트리 사용 | |
| 내림차순으로 정렬하려면 최대힙 트리 사용 | |
| 최소 힙트리 | 이진트리 종류중 하나 |
| 데이터를 순차적으로 넣으면서 루트 노드의 값이 항상 트리에서 제일 작은 값을 유지하는 트리 |
59 34 80 27 61 90 55 37 25 43
0회전 25 27 55 34 43 90 80 59 37 61
1회전 27 34 55 37 43 90 80 59 61
2회전 34 37 55 59 43 90 80 61
| 합병 | 1개만 남을 때까지 계속 두 개의 리스트로 쪼갠다. |
| 두 개의 리스트의 값들을 처음부터 비교해서 더 작은 값을 새로운 리스트에 옮긴다. |
|
| 둘 중에 하나가 끝날 때까지 반복 | |
| 둘 중에 하나가 끝나면 나머지 리스트의 값을 전부 새로운 리스트로 옮긴다. |
0회전 59 34 80 27 61 90 55 37 25 43
쪼갠 리스트들 새로운 리스트 새로운 리스트 새로운 리스트 새
59 34 80 27 61
59 34
59 34 59 34 59 80 27 34 55 59 61 80 90 25 27 34 37 43 55 59 61 80 90
34
80 27 61
80 80
27 61
27 27 61 27 55 61 90
61
90 55 37 25 43
90 55
90 55 90
55
37 25 43
37 37 25 37 43
25 43
25 25 43
43
'bootcamp > Java' 카테고리의 다른 글
| 1212 깊이우선탐색(DFS)/너비우선탐색(BFS) (1) | 2023.12.22 |
|---|---|
| 1211 동적프로그래밍 (1) | 2023.12.22 |
| 1206 AVL Tree (0) | 2023.12.22 |
| 1206 Red Black Tree (0) | 2023.12.22 |
| 1206 B-Tree (1) | 2023.12.22 |
