제 5장: 정렬과 검색(3)

52. 최소 값(최대 값)을 골라 이미 정렬된 마지막 요소와 교환하는 단순 선택 정렬

• 1~100 숫자가 적힌 카드를 오름차순으로 정렬할 때의 작업 순서

  • 카드 중 가장 숫자가 작은 카드를 찾는다
  • 1번의 카드를 오름차 순으로 나열하는 곳 왼쪽으로 옮긴다.
  • 남은 카드 중 가장 숫자가 작은 카드를 찾는다
  • 3번 카드를 오름차 순으로 정렬하는 카드의 끝에 둔다.

• 정렬할 데이터가 저장된 배열 DATA를 오름차순으로 정렬할 때의 순서

  1단계; 정렬되지 않은 부분 안에서 최소 값을 찾는다

  2단계: 최소값을 선택해 정렬되지 않은 부분의 1번째 요소와 교환한다(이 작업으로 최소 값을 정렬된 부분의 마지막 요소로 만든다)

  3단계: 정렬되지 않은 부분의 시작 위치를 1칸 뒤로 옮긴다(이 작업으로 정렬되지 않은 부분의 범위를 하나씩 줄인다)

  4단계: 정렬되지 않은 부분의 요소 수가 1일 될 때까지 1~3단계를 반복한다.

53. 이웃한 데이터들을 교환해 나가는 단순 교환 정렬(버블 정렬)

• 단순 교환 정렬: 이웃한 데이터들의 크고 작음을 따진 결과가 정렬 순서와 반대일 경우, 앞 뒤의 데이터들의 순서를 바꿔 데이터를 정렬하는 알고리즘
• 배열을 오름차 순으로 정렬하는 케이스
  • 정렬되지 않은 부분(앞부분), 정렬된 부분(뒷부분)으로 나누고, 시작할 때에는 정렬된 부분이 비어있는 상태이며, 정렬되지 않은 부분이 전체를 차지한다.
• 1단계: 정렬되지 않은 부분의 1번째 데이터와 2번째 데이터를 비교한다.
• 2단계: 1번째 데이터 > 2번째 데이터라면 순서를 바꾼다.
• 3단계: 데이터를 비교하기 시작할 위치를 뒤로 1칸 옮긴다.
• 4단계: 정렬되지 않은 부분의 데이터가 2개만 남을때까지 위의 순서를 반복한다.