049 주요 정렬 알고리즘의 이해

 

삽입 정렬 ( Insertion Sort )

ex. 8, 5, 6, 2, 4를 삽입 정렬로 정렬하시오.

• 초기 상태 :
  

  

• 1회전 :
  

  

  두 번째 값 5를 첫 번째 값과 비교하여 첫 번째 자리에 삽입하고 8을 한 칸 뒤로 이동시킨다.
• 2회전 :
  

  

  세 번째 값 6을 첫 번째, 두 번째 값과 비교하여 8자리에 삽입하고 8은 한 칸 뒤로 이동시킨다.
• 3회전 :

  

  네 번째 값 2를 처음부터 비교하여 맨 처음에 삽입하고 나머지를 한 칸씩 뒤로 이동시킨다.
• 4회전 :

  

  다섯 번째 값 4를 처음부터 비교하여 5자리에 삽입하고 나머지를 한 칸씩 뒤로 이동시킨다.

---

버블 정렬 ( Bubble Sort )

ex. 8, 5, 6, 2, 4를 버블 정렬로 정렬하시오.

• 초기 상태 :

  

• 1회전 :

  

• 2회전 :

  

• 3회전 :

  

• 4회전 :

  

---

선택 정렬 ( Selection Sort )

ex. 8, 5, 6, 2, 4를 선택 정렬로 정렬하시오.

• 초기 상태 :

  

• 1회전 :

  

• 2회전 :

  

• 3회전 :

  

• 4회전 :

  

---

2-Way 합병 정렬 ( Merge Sort )

ex. 71, 2, 38, 5, 7, 61, 11, 26, 53, 42를 2-Way 합병 정렬로 정렬하시오.

• 1회전 : 2개씩 묶은 후 각각의 묶음 안에서 정렬합니다.

  

• 2회전 : 묶여진 묶음을 2개씩 묶은 후 각각의 묶음 안에서 정렬합니다.
  

  

• 3회전 : 묶여진 묶음을 2개씩 묶은 후 각각의 묶음 안에서 정렬합니다.

  

• 4회전 : 묶여진 묶음 2개를 하나로 묶은 후 정렬합니다.

  

---

퀵 정렬 ( Quick Sort )

• 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법이다.
• 정렬 방식 중에서 가장 빠른 방식이다.
• 프로그램에서 되부름을 이용하기 때문에 스택( Stack )이 필요하다.
• 분할( Divide )과 정복( Conquer )을 통해 자료를 정렬한다.
  - 분할( Divide ) : 정렬한 자료들을 기준값인 피봇( Pivot )을 중심으로 2개의 부분집합으로 나누는 것
  - 정복( Conquer ) : 부분집합의 원소들 중 피봇( Pivot )보다 작은 원소들은 왼쪽, 피봇( Pivot )보다 큰 원소들은 오른쪽 부분집합으로 정렬하는 과정을 거치는데, 부분집합의 크기가 더 이상 나누어질 수 없을 때까지 분할과 정복을 반복 수행함

---

길벗알앤디 (강윤석, 김용갑, 김우경), 정보처리 산업기사 필기 1권 핵심요약, 길벗(2019), p 54-55.