정렬 알고리즘 (1)

정렬의 기본 개념과 관련 용어를 살펴보고, 정렬할 원소의 개수가 작을 때 간편하게 사용될 수 있는 간단하고 기본적인 성능의 비교 기반의 내부 정렬 알고리즘인 버블 정렬, 선택 정렬, 삽입 정렬, 셸 정렬에 대해서 학습한다.

 

 학습목표

• 정렬과 관련된 용어 및 개념을 이해할 수 있다.

---

• 버블 정렬의 개념, 동작, 그리고 성능과 특징을 이해할 수 있다.

---

• 삽입 정렬의 개념, 동작, 그리고 성능과 특징을 이해할 수 있다.

---

• 선택 정렬의 개념, 동작, 그리고 성능과 특징을 이해할 수 있다.

---

• 셸 정렬의 개념, 동작, 그리고 성능과 특징을 이해할 수 있다.

정렬?

• 여러 데이터로 구성된 리스트에서 값의 크기 순서에 따라 데이터를 재배치하는 것
  • 내부 정렬 - 모든 데이터 주기억장치에 저장 후 정렬
  • 외부 정렬 - 외부 기억 장치에서 주기억 장치로 불러와서 정렬
• 정렬 방식
  • 비교 기반 알고리즘 (내부 정렬) - 키 값의 비교 횟수로 성능 평가 
    • 버블 정렬, 선택 정렬, 삽입 정렬, 셀 정렬
    • 합병 정렬, 퀵 정렬, 힙 정렬 
  • 데이터 분포 기반 알고리즘 - 자료의 이동 횟수로 성능을 평가
    • 계수 정렬, 기수 정렬 - (선형 시간 복잡도) 
• 안정적 stable 정렬
  • 동일한 값을 갖는 데이터가 여러 개 있을 때, 정렬 전의 상대적인 순서가 정렬 후에도 그대로 유지되는 정렬 방식
• 제자리 in-place 정렬
  • 입력 데이터를 저장하는 공간 이외에 추가적인 저장공간을 상수 개만 필요로 하는 정렬 방식
  • 입력 크기 n이 증가함에도 불구하고 추가적인 저장공간은 증가하지 않음
• 기본 가정
  • 양의 정수, 오름 차순

버블 정렬 

• 모든 인접한 두 값을