sorting algorithm

bubble sort

인접한 두 원소의 크기를 비교하여 교환하면서 정렬

첫번째 원소와 두번째 원소, 두번째 원소와 세번째 원소 비교, ... , n-1번째 원소와 n번째 원소 이런식으로 인접한 원소를 비교하고 교환하면서 정렬

ex) 배열이 [3, 2, 1, 4, 7, 6, 5] 일때
1. 첫번째 원소 3과 두번째 원소 2를 비교 => 3 > 2 이므로 교환
[2, 3, 1, 4, 7, 6, 5]

2. 두번째 원소 3과 세번째 원소 1을 비교 => 3 > 1 이므로 교환
   [2, 1, 3, 4, 7, 6, 5]

3. 세번째 원소 3과 네번째 원소 4를 비교 => 4 > 3 이므로 교환x
   [2, 1, 3, 4, 7, 6, 5]

4. 네번째 원소 4와 다섯번째 원소 7을 비교 => 7 > 4 이므로 교환x
   [2, 1, 3, 4, 7, 6, 5]

5. 다섯번째 원소 7과 여섯번째 원소 6을 비교 => 7 > 6 이므로 교환
   [2, 1, 3, 4, 6, 7, 5]

6. 여섯번째 원소 7과 일곱번째 원소 5를 비교 => 7 > 5 이므로 교환
   [2, 1, 3, 4, 6, 5, 7]

1회전 종료

1. 첫번째 원소 2와 두번째 원소 1을 비교 => 2 > 1 이므로 교환
   [1, 2, 3, 4, 6, 5, 7]

... 생략 ...

5. 다섯번째 원소 6과 여섯번째 원소 5를 비교 => 6 > 5 이므로 교환
   [1, 2, 3, 4, 5, 6, 7]

정렬 완료

insert sort

삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.

ex) 배열이 [3, 2, 1, 4, 7, 6, 5] 일때
1. 두번째 원소인 2를 선택, 첫번째 원소인 3과 비교 => 3 > 2 이므로 3을 뒤로 한칸이동하고 2를 첫번째 자리에 배치
[2, 3, 1, 4, 7, 6, 5]

2. 세번째 원소인 1을 선택, 두번째 원소인 3과 비교 => 3 > 1 이므로 3을 뒤로 한칸 이동
   1을 첫번째 원소인 2와 비교 => 2 > 1 이므로 2를 뒤로 한칸 이동하고 1을 첫번째 자리에 배치
   [1, 2, 3, 4, 7, 6, 5]

3. 여섯번째 원소인 6을 선택, 다섯번째 원소인 7과 비교 => 7 > 6 이므로 7을 한칸 뒤로 이동하고 6을 다섯번째 자리에 배치
   [1, 2, 3, 4, 6, 7, 5]

4. 일곱번째 원소인 5를 선택, 여섯번째 원소인 7과 비교 => 7 > 5 이므로 7을 뒤로 한칸 이동
   5를 다섯번째 원소인 6과 비교 => 6 > 5 이므로 6을 뒤로 한칸 이동하고 5를 다섯번째 자리에 위치
   [1, 2, 3, 4, 5, 6, 7]

정렬 완료

selection sort

크기가 가장 큰 원소를 찾고 맨 오른쪽 원소와 교환을 반복하여 정렬

ex) 배열이 [3, 2, 1, 4, 7, 6, 5] 일때
1. 크기가 가장 큰 원소인 7을 선택 => 맨 오른쪽 원소인 5와 교환
[3, 2, 1, 4, 5, 6, 7]

2. 7을 제외하고 가장 큰 원소인 6을 선택 => 바꿀 필요 없음

5, 4는 같은 방식으로 생략

3. 4, 5, 6, 7을 제외하고 가장 큰 원소인 3을 선택 => [3, 2, 1]에서 맨 오른쪽 원소인 1과 교환
   [1, 2, 3, 4, 5, 6, 7]

정렬 완료