[Algorithm #정리] Python의 sorting 알고리즘 및 예제 코드

• 정렬(Sorting)

  • 데이터를 특정 기준에 따라 순서대로 나열하는 것.

• 정렬 알고리즘

  • selection sort (선택정렬)

    • 가장 작은것 탐색 ⇒ 자리 변경 ⇒ 반복
    • 시간복잡도
      • N-1만큼 작은것 탐색, {N*(N+1)}/2 ⇒ O(N^2)

  • insertion sort (삽입 정렬)

    • 하나씩 ⇒ 적절한 위치에 삽입
    • 무조건 자리를 바꾸는 선택정렬과의 차이 ⇒ 삽입정렬은 필요시에만 자리 변경 발생
    • 시간복잡도
      • 반복문 2번 사용
      • O(N^2), 단 최선(완벽하게 정렬된)의 경우 O(N)

  • quick sort (퀵 정렬)

    • 기준이 되는 요소(pivot)지정, 한쪽 끝 ⇒ 한쪽은 pivot보다 작은것, 다른쪽은 pivot보다 큰 것⇒ 큰 것 ↔ 작은 것 자리 교환 ⇒ 반복 ⇒ 큰 것 탐색과 작은 것 탐색 간 교차 발생 시 ⇒ 작은 것 ↔ pivot 간 자리 교환(분할, partition 발생) → 파티션 기준 데이터 분할 발생 ⇒ pivot 다시 선정 ⇒ 반복 ⇒ 분할된 리스트의 요소가 1이거나 비는 경우 ⇒ 종료
    • 시간복잡도
      • 평균 O(NlogN)
      • 단, 최악의 경우 O(N^2). 데이터가 이미 정렬되어 있는 경우다.
    • <code1>

    array=[5,7,9,0,3,1,6,2,4,8]
    def quick_sort(array, start, end):
        if start >= end:
            return
        pivot = start
        print('pivot element is ',pivot, end=':')
        left = start+1
        right=end
        while left<=right:
            while left<=end and array[left] <= array[pivot]:
                left+=1
            while right > start and array[right] >= array[pivot]:
                right -= 1
            if left > right:
                array[right], array[pivot] = array[pivot], array[right]
                print(array)
            else:
                array[left], array[right] = array[right], array[left]
        quick_sort(array, start, right-1)
        quick_sort(array, right + 1, end)
    if __name__ == "__main__":
        quick_sort(array, 0, len(array)-1)
        print(array)
    

    • <code2>

    array=[5,7,9,0,3,1,6,2,4,8]
    def quick_sort(array):
        if len(array) <= 1:
            return array
        pivot = array[0]
        tail = array[1:]
        left_side = [x for x in tail if x <= pivot]
        right_side = [x for x in tail if x > pivot]
        #분할 이후 왼쪽부분, 오른쪽 부분에서 각각 정렬 수행, 전체 리스트 반환
        return quick_sort(left_side)+[pivot]+quick_sort(right_side)
    if __name__ == "__main__":
        print(quick_sort(array))
    

  • count sort (계수정렬)

    • 별도의 0으로 초기화된 리스트 생성(단, 최대값과 최소값의 범위만큼) ⇒ 값 하나씩 대응되는 Indexd의 데이터 크기를 증가시킨다 ⇒ index의 값 만큼 데이터를 출력 또는 빈 리스트에 담아 정렬
    • 가장 큰 데이터 - 가장 작은 데이터 간 차이가 크면 ⇒ 매우 비효율적 또는 사용불가(정수 범위를 넘어서는 경우, 리스트 사이즈를 초과할 수 있으므로)
    • 정수인 배열만 가능하다(양수인 경우만)
    • 시간복잡도
      • 데이터의 개수 N, 최대값의 크기 K
      • 평균 O(N+K)
        • 앞에서 부터 데이터를 하나씩 확인, 리스트에서 적절한 인덱스 값 1씩 증가
        • 인덱스의 값 확인 시 K 만큼 소요되므로.
    • 심각한 메모리 낭비, 비효율 초래가 가능하다는 단점
    • <code>

    array=[7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
    count=[0]*(max(array)+1) #범위만큼 사이즈를 가지는 별도의 리스트 0으로 초기화 하여 생성
    for i in range(len(array)):
        count[array[i]]+=1
    for i in range(len(count)):
        for j in range(count[i]):
            print(i, end=' ')
    

• Python에서의 정렬

• sorted(array)
  • array를 리스트 하여 리턴함.
  • 별도의 변수로 받아줘야 함.
• array.sort()
  • 별도의 리턴 없이 array를 정렬
• sort()/sorted() 모두 별도의 key parameter를 받을 수 있다.
  • 정렬 기준을 key에 맞춰 이뤄진다.
• <code>
• array=[5,7,9,0,3,1,6,2,4,8]

  
  

  sorted_arr = sorted(array)

  print('sorted() : ',sorted_arr)

  
  

  array=[5,7,9,0,3,1,6,2,4,8]

  array.sort()

  print('sort() : ',array)
•