[필기] 정보처리기사 7강

TOPIC : 정렬(SORT)

정렬파트에서 빈출 ↑, 구분하는 방법과 N회전시의 정렬방법 구분 요.

1. 정렬 (SORT)

1. 내부정렬 (Internal Sort)
   • 데이터 량이 적을 때 주기억 장치 내에서 정렬하는 방법
   • 주기억장치 내에서? = 주기억장치는 내부에 있는 만큼 속도가 빠르지만 정확한 정보 저장 X
   • 내부정렬이 주기억장치라면 그 반대는 외부정렬이 보조기억장치? = 맞음
   • 종류는 삽입, 쉘, 버블, 퀵, 선택, 히프, 2 Way Merge 등이 있지만 주요파트 세 개만 다뤄보자.
     1. 선택정렬(Insertion Sort)
        • 맨 앞에 있는 값을 선택한 뒤, 술게임 훈민정음처럼 모든 데이터와 비교 및 교환
        • EX) "85264"를 오름차순 정렬한다 하면 8을 5,2,6,4 순서로 비교해서 바꿈
          1회전 : 58264, 28564
          2회전 : 25864, 24865
          3회전 : 24685, 24586
          4회전 : 24568 (오름차순 정렬 완료) , 선택정렬시 제일 작은 수가 맨 앞으로 감.
     2. 버블정렬(Bubble Sort)
        • 나와 내옆에 나와 내옆에 나와 내옆에 나와...
        • 서로 인접한 두 개의 값을 비교하여 기준에 따라 교환한다. (즉, 두 개씩 묶어서 겹치게)
        • 선택정렬과 달리 제일 큰 수가 맨 뒤로 가게됨
        • EX) "85264"를 오름차순 정렬한다 하면, [(8,5),2,6,4]로 묶어 비교함
          1회전 : 58264, 52864, 52684, 52648 (제일 큰 수가 맨 뒤로감)
          2회전 : 25648, 25468
          3회전 : 24568
     3. 삽입정렬(Insertion Sort)
        1. 이미 정렬된 파일에 새로운 레코드를 위치에 맞게 삽입한다. / AND조건 느낌인듯
        2. EX) [(8,5)2,6,4] 처럼 264에서 계속 물어본다.
           1회전 : 2은 8보다 큰가? / NO 5보다 작은가? / YES
           = THEN 맨 앞으로 삽입... 순서로 묶은 애들이랑 계속 비교해가는 것.
2. 외부정렬 (External Sort)
   • 얘네들 아니라면 내부정렬이겠구나! / 종류 문제정도로 사용.
     1. 균형 합병 정렬 (Balanced Sort)
     2. 다단계 합병 정렬 (Polyphase Sort)
     3. 계단식 합병 정렬 (Cascade Sort)
     4. 진동 병합 정렬 (Oscillating Sort)