정렬 기본

• 개념

  --> 자료들을 일정한 순서대로 나열하는 것

  정렬 알고리즘의 종류

  1) 선택 정렬
  2) 삽입 정렬
  3) 버블 정렬
  4) 퀵 정렬

• 선택 정렬

  --> 여러 데이터 중에서 가장 작은 값을 뽑는 작동을 반복하여 값을 정렬하는 방식
  --> 가장 작은 데이터를 계속적으로 뽑아 오름차순 정렬을 시도한다.
  --> 사이클의 크기가 전체에서 시작해 점점 작아진다.
  ex) 데이터 4개를 선택정렬
  1번째 사이클 : 0 vs 1 (유지), 0 vs 2 (변경), 2 vs 3 ==> 데이터 갯수 - 1
  2번째 사이클 : 1 vs 2 (변경), 2 vs 3 (유지) ==> 데이터 갯수 - 2
  3번째 사이클 : 2 vs 3 ==> 데이터 갯수 - 3
  * 결론: 사이클 맨 앞의 데이터를 바로 뒤 데이터부터 순서대로 비교 -> 작은 데이터가 나오면 해당 데이터 뒤의 데이터는 작은 데이터와 비교

  최솟값을 찾는 방법

  --> 가장 작은 값을 찾는 함수
  1) 배열의 첫 번째 값을 가장 작은 값으로 지정
  2) 다음 차례의 값과 비교하여 작은 값을 변경 or 그대로 둠

  def findMinIdx(ary):
     minIdx = 0 # 배열의 초기값을 최솟값으로 지정
     for i in range(1, len(ary)): # 비교 반복
         if (ary[minIdx] > ary[i]):
             minIdx = i 
         return minIdx
  testAry = [55, 88, 33, 77]
  minPos = finMinIdx(testAry)
  print(testAry[minPos])

  선택 정렬 구현

  가변 크기의 빈 배열 사용

  ary = []
  ary.append(100)
  ary.append(200)
  # 길이가 2인 배열로 바뀜

  두 변수 값 교환

  --> 원칙적으로 한 번에 두 변수의 값을 교환하는 것은 불가능
  --> 임시 공간을 사용한다.
  1)

  temp = A
  A = B
  B = temp

  2)

  A, B = B, A

  개선된 선택 정렬 구현

  * 기존의 선택 정렬 구현 방법에는 배열을 전, 후로 2개 사용하였다.
  --> but, 배열 1개로 데이터를 정렬하는 것이 효율적
  1) 첫 번째 사이클
  데이터 전체 중 맨 앞 데이터를 최솟값으로 지정 -> 최솟값과 나머지 데이터의 크기 비교 ==> 반복 횟수 n-1 + index가 0인 데이터와 최솟값 데이터 변경
  2) 두 번째 사이클
  맨 앞 데이터를 제외하고 두 번째 데이터를 최솟값으로 지정 -> 크기 비교 ==> 반복 횟수 n-2 + index가 1인 데이터와 최솟값 데이터 변경
  .......반복
  3) 마지막 사이클
  맨 뒤에서 두 번째 데이터와 맨 뒤 데이터 비교 ==> 반복 횟수 1
  cycle 수: (n-1) + (n-2) + .... + 1 = n * (n-1) / 2

  구현 코드

  def selectionSort(ary):
      n = len(ary)
      for i in range(0, n-1): # 처음부터 끝까지 비교
          minIdx = i
          for k in range(i+1, n-1):
              if (ary[minIdx] > ary[k]):
                  minIdx = k
          ary[i], ary[minIdx] = ary[minIdx], ary[i]
      return ary
  ## 전역 변수 선언 부분 ##
  dataAry = [188, 162, 168, 120, 50, 150, 177, 105]
  print('before sorting --> ', dataAry)
  print('after sorting --> ', selectionSort(dataAry))

  성능

  사이클 횟수 : n * (n-1) / 2
  연산 수 : O(n^2)

• 삽입 정렬

  --> 기존 데이터 중에서 자신의 위치를 찾아 데이터를 삽입하는 정렬 방식
  --> 맨 앞의 데이터 부터 크기에 맞춰서 새로운 배열에 삽입한다.
  --> 사이클의 크기가 맨 앞의 2개부터 시작해 점점 커진다.
  ex) 데이터 4개를 삽입 정렬
  1번째 사이클 : 1 vs 0 ==> 1
  2번째 사이클 : 2 vs 1, 2 vs 0 ==> 2
  3번째 사이클 : 3 vs 2, 3 vs 1, 3 vs - ==> 3

삽입 위치를 찾는 방법

def findInsertIdx(ary, data):
   findIdx = -1 # 초깃값은 없는 위치
   for i in range(0, len(ary)):
       if (ary[i] > data):
           findIdx = i # 삽입할 데이터가 해당 위치 데이터보다 작으면 해당 위치에 삽입
           break
       if findIdx == -1: 큰 값을 못 찾음
           return len(ary) # 맨 뒤
       else:
           return findIdx # 해당 위치

삽입 정렬 구현

insert 함수

insert(삽입할 위치, 값) --> 해당 위치에 해당 값을 삽입시켜주는 함수

삽입 정렬의 효율적인 구현

--> 배열 1개로 삽입 정렬 구현
--> 해당 사이클의 마지막 값을 현재 값으로 두기
1) 1번째 사이클
맨 앞 2개의 데이터 비교 ==> 반복 수 : 1
2) 2번째 사이클
맨 앞 3개의 데이터 비교 ==> 반복 수 : 2

구현 코드

def insertionSort(ary):
    n = len(ary)
    for end in range(1, n): # end --> 현재
        for cur in range(end, 0, -1): # 현재에서 맨 처음까지 비교
            if (ary[cur-1] > ary[cur]):
                ary[cur-1], ary[cur] = ary[cur], ary[cur-1]
        return ary

성능

연산 수 : O(n^2)

• 정리

  1) 선택 정렬
  현재 데이터 : 해당 사이클의 맨 처음 데이터
  방식 : 현재 데이터를 바로 뒤의 데이터부터 사이클의 맨 뒤 데이터까지 비교하면서 정렬
  사이클 크기 : 전체에서 맨 뒤의 2개까지 점점 줄어든다.

  2) 삽입 정렬
  현재 데이터 : 해당 사이클의 맨 마지막 데이터
  방식 : 현재 데이터를 바로 앞의 데이터부터 사이클의 맨 앞 데이터까지 비교하면서 정렬
  사이클 크기 : 맨 앞의 2개부터 전체까지 점점 커진다.