알고리즘 - 정렬 알고리즘 (선택 정렬, 삽입 정렬, 버블 정렬)

 

선택 정렬

• 원리: 배열에서 가장 작은(큰) 데이터를 찾아 맨 앞 데이터와 교환
• 특징: 단순하지만 비효율적, 교환 횟수가 적음
• 공간 복잡도: O(1)
• 시간 복잡도: O(n^2)
• 예시

[3, 2, 4, 1]
→ [1, 2, 4, 3] // 1
→ [1, 2, 4, 3] // 2
→ [1, 2, 3, 4] // 3

1. [3, 2, 4, 1] 중 가장 작은 수를 찾음 → 1
   • 1과 인덱스 0번 데이터(3) 과 교환 → [1, 2, 4, 3]
2. 인덱스를 증가시켜 인덱스 1번 이후 [2, 4, 3] 중 가장 작은 수를 찾음 → 2
   • 인덱스 1번 데이터(2)와 스왑 → [1, 2, 4, 3]
3. 인덱스를 증가시켜 인덱스 2번 이후 [4, 3] 중 가장 작은 수를 찾음 → 3
   • 인덱스 2번 데이터(4)와 스왑 → [1, 2, 3, 4]

 

삽입 정렬

• 원리: 데이터를 하나씩 정렬된 부분에 삽입하여 정렬함
• 특징: 데이터가 거의 정렬된 경우 효율적, 적은 양의 데이터에 적합
• 공간 복잡도: O(n)
• 시간 복잡도: O(n^2)
• 예시

[3, 2, 4, 1] // 1
→ [2, 3, 4, 1] // 2
→ [2, 3, 4, 1] // 3
→ [1, 2, 3, 4] // 4

1. 우선 정렬된 부분은 인덱스 0번(3)으로 두고 2, 4, 1 순으로 삽입할거임
   • [3]
2. 정렬된 부분에서 삽입되는 값(2)을 올바른 위치에 삽입함 → 2는 3보다 작은 앞에 삽입
   • [2, 3]
3. 다음 삽입되는 값(4)를 올바른 위치에 삽입 → 3보다 크므로 3뒤에 삽입
   • [2, 3, 4]
4. 다음 삽입되는 값(1)를 올바른 위치에 삽입 → 2보다 작으므로 2 앞에 삽입
   • [1, 2, 3, 4]

→ 최악의 경우 삽입을 위해 이미 정렬된 배열의 값을 모두 탐색해야 하므로 비효율적

 

 

버블 정렬

• 원리: 인접한 두 데이터를 비교하여 순서가 잘못된 경우 교환하여 큰 데이터를 뒤로 보냄
• 특징: 단순하지만 비효율적이며, 소규모 데이터 정렬에 적합
• 공간 복잡도: O(1)
• 시간 복잡도: O(n^2)
• 예시

[3, 2, 4, 1]
→ [2, 3, 4, 1] // 1.
→ [2, 3, 1, 4] // 2. 
→ [2, 1, 3, 4] // 3.
→ [1, 2, 3, 4] // 4.

1. 3, 2를 비교하여 더 큰 수를 뒤로 보냄
2. 3, 4는 제대로 되어 있으므로 4, 1 비교 후 스왑 → [2, 3, 1, 4]
3. 다시 처음부터 2, 3 비교, 3, 1 비교 후 스왑 → [2, 1, 3, 4] , 3, 4 비교
4. 다시 처음부터 2, 1 비교 후 스왑 → [1, 2, 3, 4] 2, 3 비교, 3, 4 비교