레코드 정렬 방식

삽입 정렬 (Insertion Sort)

정의: 이미 정렬된 부분에 새로운 값을 순서에 맞게 삽입하여 정렬하는 방식.
시간 복잡도: 평균 및 최악 모두 O(n²).

예시: 8, 5, 6, 2, 4

• 초기 상태: 8, 5, 6, 2, 4
• 1회전: 8, 5 → 5, 8
  • 두 번째 값 5를 첫 번째 값 8과 비교하여 5가 더 작으므로 교체.
• 2회전: 5, 8, 6 → 5, 6, 8
  • 세 번째 값 6을 두 번째 값 8과 비교하여 6이 더 작으므로 교체.
• 3회전: 5, 6, 8, 2 → 2, 5, 6, 8
  • 네 번째 값 2를 첫 번째부터 비교하여 맨 앞에 삽입.
• 4회전: 2, 5, 6, 8, 4 → 2, 4, 5, 6, 8
  • 다섯 번째 값 4를 두 번째 값 5와 비교하여 5 앞에 삽입.

---

선택 정렬 (Selection Sort)

정의: 배열에서 가장 작은 값을 찾아 첫 번째 자리에 놓고, 그다음 작은 값을 찾아 두 번째 자리에 놓는 방식을 반복하는 정렬 방식.
시간 복잡도: 평균 및 최악 모두 O(n²).

예시: 8, 5, 6, 2, 4

• 초기 상태: 8, 5, 6, 2, 4
• 1회전: 8, 5, 6, 2, 4 → 5, 8, 6, 2, 4 → 5, 8, 6, 2, 4 → 2, 8, 6, 5, 4
  • 가장 작은 값 2를 찾아 첫 번째 값과 교체.
• 2회전: 2, 8, 6, 5, 4 → 2, 6, 8, 5, 4 → 2, 5, 8, 6, 4 → 2, 4, 8, 6, 5
  • 두 번째 값부터 가장 작은 값 4를 찾아 두 번째 값과 교체.
• 3회전: 2, 4, 8, 6, 5 → 2, 4, 6, 8, 5 → 2, 4, 5, 8, 6
  • 세 번째 값부터 가장 작은 값 5를 찾아 교체.
• 4회전: 2, 4, 5, 8, 6 → 2, 4, 5, 6, 8
  • 네 번째 값부터 가장 작은 값 6을 찾아 교체.

---

버블 정렬 (Bubble Sort)

정의: 인접한 두 값의 크기를 비교하여 자리 교환을 통해 큰 값을 뒤로 보내는 방식으로 정렬.
시간 복잡도: 평균 및 최악 모두 O(n²).

예시: 8, 5, 6, 2, 4

• 초기 상태: 8, 5, 6, 2, 4
• 1회전: 8, 5 → 5, 8 → 5, 6, 8 → 5, 6, 2, 8 → 5, 6, 2, 4, 8
  • 인접한 값을 비교하여 더 큰 값 8을 뒤로 이동.
• 2회전: 5, 6, 2, 4, 8 → 5, 2, 6, 4, 8 → 5, 2, 4, 6, 8
  • 두 번째로 큰 값 6을 뒤로 이동.
• 3회전: 5, 2, 4, 6, 8 → 2, 5, 4, 6, 8 → 2, 4, 5, 6, 8
  • 세 번째로 큰 값 5를 뒤로 이동.
• 4회전: 2, 4, 5, 6, 8 (정렬 완료)

---

퀵 정렬 (Quick Sort)

정의: 피벗 값을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누어 정렬하는 방식.
시간 복잡도: 평균 O(nlogn), 최악 O(n²).

예시: 8, 5, 6, 2, 4 (피벗 값: 4)

• 초기 상태: 8, 5, 6, 2, 4
• 1단계 분할: [8, 5, 6, 2, 4] → [2], [4, 5, 6, 8]
  • 피벗 값 4를 기준으로 2는 왼쪽, 나머지는 오른쪽에 배치.
• 2단계 분할: [2], [4, 5, 6, 8] → [2], [4], [5, 6, 8]
  • 피벗 값 5를 기준으로 다시 분할.
• 최종 정렬: [2, 4, 5, 6, 8] (정렬 완료)